Why Is Maximum Clique Often Easy in Practice?

Jose L. Walteros () and Austin Buchanan ()
Additional contact information
Jose L. Walteros: Department of Industrial and Systems Engineering, University at Buffalo, Buffalo, New York 14260
Austin Buchanan: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078

Operations Research, 2020, vol. 68, issue 6, 1866-1895

Abstract: To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with 1,000 vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks? In this paper, we provide an explanation. First, we observe that the graph’s clique number ω is very near to the graph’s degeneracy d in most real-life instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap g ≔ ( d + 1 ) − ω between the clique number ω and its degeneracy-based upper bound d +1. When this gap g can be treated as a constant, as is often the case for real-life graphs, the proposed algorithm runs in time O ( d m ) = O ( m 1.5 ) . This provides a rigorous explanation for the apparent easiness of these instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature.

Keywords: maximum clique; fixed-parameter tractable; fpt; vertex cover; degeneracy; k-core; parameterized below degeneracy; kernelization; parameterized complexity (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1970 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:6:p:1866-1895

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().