  


Why is maximum clique often easy in practice?
Jose L. Walteros (josewaltbuffalo.edu) Abstract: To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers' best efforts, there exist unsolved benchmark instances with one thousand vertices. However, relatively simple algorithms solve reallife 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 $\omega$ is very near to the graph's degeneracy $d$ in most reallife 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)\omega$ between the clique number $\omega$ and its degeneracybased upper bound $d+1$. When this gap $g$ can be treated as a constant, as is often the case for reallife graphs, the proposed algorithm runs in time $O(dm)=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 practicalcompetitive with the best approaches from the literature. Keywords: maximum clique; fixedparameter tractable; fpt; vertex cover; degeneracy; $k$core; parameterized below degeneracy; kernelization; parameterized complexity. Category 1: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 07/12/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  