An exact algorithm for the maximum quasi‐clique problem
Celso Carneiro Ribeiro, José Angel Riveaux · International Transactions in Operational Research · 2019
Abstract Given a graph and a threshold , the maximum quasi‐clique problem amounts to finding a maximum cardinality subset of the vertices in V such that the edge density of the graph induced in G by 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.