Finding Small Complete Subgraphs Efficiently

Abstract

(I) We revisit the algorithmic problem of finding all triangles in a graph $G=(V,E)$ with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in $O(m \alpha ) = O(m^{3/2})$ time, where $\alpha = \alpha (G)$ is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s.

(II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on m and $\alpha$ in the running time $O(\alpha ^{\ell -2} \cdot m)$ of the algorithm of Chiba and Nishizeki for listing all copies of $K_\ell$, where $\ell \ge 3$, is asymptotically tight.

(III) We give improved arboricity-sensitive running times for counting and/or detection of copies of $K_\ell$, for small $\ell \ge 4$. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every $\ell \ge 7$.