An exact algorithm for the maximum quasi-clique problem

Given a graph G=(V,E) and a threshold gamma is an element of(0,1], the maximum quasi-clique problem amounts to finding a maximum cardinality subset C* of the vertices in V such that the edge density of the graph induced in G by C* is greater than or equal to the threshold. This problem is NP-hard and has a number of applications in data mining, for example, in social networks or phone call graphs. In this work, we present an exact algorithm to solve this problem, based on a quasi-hereditary property. We also propose a new upper bound that is used for pruning the search tree. Numerical results show that the new approach is competitive and outperforms the best integer programming approaches in the literature. The new upper bound is consistently tighter than previously existing bounds.