Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs Academic Article uri icon

abstract

  • © 2015, Springer Science+Business Media New York. Given a simple graph and a constant (Formula presented.) , a (Formula presented.) -quasi-clique is defined as a subset of vertices that induces a subgraph with an edge density of at least (Formula presented.). This well-known clique relaxation model arises in a variety of application domains. The maximum (Formula presented.) -quasi-clique problem is to find a (Formula presented.) -quasi-clique of maximum cardinality in the graph and is known to be NP-hard. This paper proposes new mixed integer programming (MIP) formulations for solving the maximum (Formula presented.) -quasi-clique problem. The corresponding linear programming (LP) relaxations are analyzed and shown to be tighter than the LP relaxations of the MIP models available in the literature on sparse graphs. The developed methodology is naturally generalized for solving the maximum (Formula presented.) -dense subgraph problem, which, for a given function (Formula presented.) , seeks for the largest k such that there is a subgraph induced by k vertices with at least f(k) edges. The performance of the proposed exact approaches is illustrated on real-life network instances with up to 10,000 vertices.

author list (cited authors)

  • Veremyev, A., Prokopyev, O. A., Butenko, S., & Pasiliao, E. L.

citation count

  • 22

publication date

  • November 2015