BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Clique Is Hard for State-of-the-Art Algorithms de Rezende, Susanna


Finding a maximum clique in a graph is one of the most basic computational problems on graphs. The various applications of this problem has motivated the design of algorithms which today can successfully solve real-world instances with thousands of vertices. However, from a theoretical point a view, it is widely believed that this is a hard problem: in particular that determining whether a graph on n vertices contains a k-clique requires time $n^{\Omega(k)}$. In terms of upper bounds, it is easy to determine this in time roughly $n^k$ by checking if any of the sets of vertices of size k forms a clique.

We analyse the running time of the most successful algorithms used in practice: colour-based branch-and-bound strategies and à stergård's algorithm based on Russian doll search. When analysing such algorithms, it is convenient to view the execution trace as a proof establishing the maximal clique size for the input graph. In particular, if this graph does not have a k-clique, then the trace provides an efficiently verifiable proof in so-called regular resolution of the statement that the graph is k-clique-free. We show that for any $k \ll n^{1/4}$ if the input graph is a k-clique-free random graph sampled from the right distribution then the size of such regular resolution proofs, and hence the running time of these algorithm, is at least $n^{\Omega(k)}$.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International