On the maximum quasi-clique problem

AbstractGiven 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<γ