Abstract
We study finding and listing $k$-cliques in a graph, for constant $k\geq 3$, a fundamental problem of both theoretical and practical importance. Our main contribution is a new output-sensitive algorithm for listing $k$-cliques in graphs, for arbitrary $k\geq 3$, coupled with lower bounds based on standard fine-grained assumptions, showing that our algorithm's running time is tight. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of $3$-cliques by Bj"{o}rklund, Pagh, Vassilevska W. and Zwick [ICALP'14]. Typical inputs to subgraph isomorphism or listing problems are measured by the number of nodes $n$ or the number of edges $m$. Our framework is very general in that it gives $k$-clique listing algorithms whose running times are measured in terms of the number of $\ell$-cliques $\Delta_\ell$ in the graph for any $1\leq \ell<k$. This generalizes the typical parameterization in terms of $n$ (the number of $1$-cliques) and $m$ (the number of $2$-cliques). If the matrix multiplication exponent $\omega$ is $2$, and if the size of the output, $\Delta_k$, is sufficiently large, then for every $\ell<k$, the running time of our algorithm for listing $k$-cliques is $$\tilde{O}\left(\Delta_\ell^{\frac{2}{\ell (k - \ell)}}\Delta_k^{1-\frac{2}{k(k-\ell)}}\right).$$ For sufficiently large $\Delta_k$, we prove that this runtime is in fact {\em optimal} for all $1 \leq \ell < k$ under the Exact $k$-Clique hypothesis. In the special cases of $k = 4$ and $5$, our algorithm in terms of $n$ is conditionally optimal for all values of $\Delta_k$ if $\omega = 2$. Moreover, our framework is powerful enough to provide an improvement upon the 19-year old runtimes for $4$ and $5$-clique detection in $m$-edge graphs, as a function of $m$ [Eisenbrand and Grandoni, TCS'04].
Introduction
In graph theory, a $k$-clique is a set of $k$ vertices where every pair is connected by an edge. Finding these structures is a cornerstone of network analysis, used in everything from identifying communities in social networks to spotting motifs in biological data. This paper breaks a 19-year stalemate by providing the first improved algorithms for finding 4- and 5-cliques in sparse graphs since 2004.
There are two main versions of this task: detection (is there at least one $k$-clique?) and listing (find all $t$ of them). While we have known how to do this for decades, the efficiency of these algorithms has hit a wall. Most traditional algorithms are "input-sensitive," meaning their speed depends only on the size of the graph ($n$ vertices or $m$ edges). This work focuses on output-sensitive algorithms, where the runtime also depends on $t$, the number of cliques actually found. If a graph has very few cliques, the algorithm should ideally run much faster.
Algorithmic Framework
The authors employ a "dense-sparse" paradigm combined with a novel recursive framework. The core innovation is parameterizing the problem using $\Delta_\ell$, the number of smaller $\ell$-cliques (where $\ell < k$). For example, to find 4-cliques, the algorithm might first look at the number of triangles (3-cliques) in the graph.
To achieve this, the algorithm treats "heavy" parts of the graph (nodes/edges involved in many cliques) differently than "light" parts. For sparse parts, it uses recursive listing in neighborhoods. For dense parts, it leverages fast rectangular matrix multiplication to aggregate connections and identify cliques en masse.
Breaking the 19-Year Stalemate
By more carefully balancing the recursion between neighborhoods and using the latest bounds on rectangular matrix multiplication, the authors shaved the exponents down for the first time since Eisenbrand and Grandoni's 2004 work. The improvements for 4-clique and 5-clique detection in $m$-edge graphs are summarized below:
Theoretical Optimality and Tightness
A significant contribution of this work is the proof that these algorithms are "conditionally optimal" under the Exact-$k$-Clique Hypothesis. This is a standard assumption in theoretical computer science that provides a "speed limit" for clique detection. By showing their listing algorithms match these limits, the authors prove their framework is as fast as theoretically possible.
This realization shows that the output-sensitive runtimes for $k > 3$ perfectly extend the known optimal results for triangles ($k=3$), creating a unified theory of clique listing. For any constant $k \geq 3$, the authors provide an algorithm that is tight under the Exact-$k$-Clique Hypothesis. If the matrix multiplication exponent $\omega$ is 2, the runtime for listing $t$ cliques is: $$\tilde{O}\left(\min\left\{m^{\frac{1}{k-2}} t^{1-\frac{2}{k(k-2)}}, n^{\frac{2}{k-1}} t^{1-\frac{2}{k(k-1)}}\right\}\right)$$
Limitations and Future Work
The "optimality" of these algorithms is tied to the current best bounds for matrix multiplication. If a breakthrough occurs in how we multiply matrices, these graph algorithms would need to be re-evaluated, though the framework itself remains valid. Additionally, as $k$ increases, the complexity of the "refined" analysis grows significantly. While the paper provides a general algorithm for all $k$, even tighter bounds might be possible for specific larger values of $k$ (like $k=6$) through more exhaustive case-by-case analysis. Finally, exploring the practical implementation of these "theoretically optimal" algorithms is a natural next step, as the hidden constants in Big-O notation may be large.
Summary updated