Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

We study the problem of finding and listing k-cliques in an m-edge, n-vertex graph, for constant k ≥ 3. This is a fundamental problem of both theoretical and practical importance.

Our first contribution is an algorithmic framework for finding k-cliques that gives the first improvement in 19 years over the old runtimes for 4 and 5-clique finding, as a function of m [Eisenbrand and Grandoni, TCS'04]. With the current bounds on matrix multiplication, our algorithms run in O(m 1.66 ) and O(m 2.06 ) time, respectively, for 4-clique and 5-clique finding.

Our main contribution is an output-sensitive algorithm for listing k-cliques, for any constant k ≥ 3. We complement the algorithm with tight lower bounds based on standard fine-grained assumptions. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of 3-cliques given by Björklund, Pagh, Vassilevska W. and Zwick [ICALP'14]. If the matrix multiplication exponent ω is 2, and if the number of k-cliques t is large enough, the running time of our algorithms is Õ minm

and this is tight under the Exact-k-Clique Hypothesis. This running time naturally extends the running time obtained by Björklund, Pagh, Vassilevska W. and Zwick for k = 3. Our framework is very general in that it gives k-clique listing algorithms whose running times can be measured in terms of the number of ℓ-cliques ∆ ℓ in the graph for any 1 ≤ ℓ < k. This generalizes the typical parameterization in terms of n (the number of 1-cliques) and m (the number of 2-cliques).

If ω is 2, and if the size of the output, ∆ k , is sufficiently large, then for every ℓ < k, the running time of our algorithm for listing k-cliques is Õ ∆

We also show that this runtime is optimal for all 1 ≤ ℓ < k under the Exact k-Clique hypothesis.