On the maximum quasi-clique problem

Given a simple undirected graph G=(V,E)G=(V,E) and a constant γ∈(0,1)γ∈(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<γ<10<γ<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.