On the maximum quasi-clique problem Academic Article uri icon

abstract

  • Given a simple undirected graph G = (V, E) and a constant γ ∈ (0, 1), a subset of vertices is called a γ-quasi-clique or, simply, a γ-clique if it induces a subgraph with the edge density of at least γ. The maximum γ-clique problem consists in finding a γ-clique of largest cardinality in the graph. Despite numerous practical applications, this problem has not been rigorously studied from the mathematical perspective, and no exact solution methods have been proposed in the literature. This paper, for the first time, establishes some fundamental properties of the maximum γ-clique problem, including the NP-completeness of its decision version for any fixed γ satisfying 0 < γ < 1, the quasi-heredity property, and analytical upper bounds on the size of a maximum γ-clique. Moreover, mathematical programming formulations of the problem are proposed and results of preliminary numerical experiments using a state-of-the-art optimization solver to find exact solutions are presented. © 2012 Elsevier B.V. All rights reserved.

author list (cited authors)

  • Pattillo, J., Veremyev, A., Butenko, S., & Boginski, V.

citation count

  • 56

publication date

  • January 2013