Exploiting star inequalities for the maximum quasi-clique problem

Mining of dense subgraphs is of substantial interest in graphbased applications where the interactions between elements encode meaningful properties of the solutions. Cohesive structures are well described by several clique relaxations. The maximum γ quasi-clique problem ask to find an induced γ quasi-clique of maximum order, i.e., the largest subgraph whose edge density is at least γ. We present a new MILP formulation obtained by the integer decomposition of star inequalities, and a surrogate relaxation whose number of constraints is linear in the number of vertices of the graph. The former provides a dual bound potentially better than that obtained by the MILP formulations available in the literature; the latter can be exploited to handle dense graphs of large size. The practicability and usefulness of the proposed mathematical programs have been assessed through extensive computational experiments.