Finding Small Complete Subgraphs Efficiently ¹¹1 A preliminary version of this paper appeared in the Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), LNCS 13889, Springer, Cham, Switzerland, 2023, pp. 185–196.

We obtain the following results for the problem of finding small complete subgraphs of a given size. Each of our algorithms for deciding whether a graph contains a given complete subgraph (item (iii) below) also finds a suitable witness, if it exists.

1. (i)

   We provide a new combinatorial algorithm for finding all triangles in a graph running in $O(m\alpha)=O(m^{3/2})$ time, where $\alpha=\alpha(G)$ is the graph arboricity (Algorithm Hybrid in Section 2). 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.

2. (ii)

   For every $n$, $b\leq n/2$ and a fixed $\ell\geq 3$, there exists a graph $G$ of order $n$ with $m$ edges and $\alpha(G)\leq b$ that has $\Omega(\alpha^{\ell-2}\cdot m)$ copies of $K_{\ell}$ (Lemma 3 in Section 3). As such, the dependency on $m$ and $\alpha$, in the running time $O(\alpha^{\ell-2}\cdot m)$ for listing all copies of $K_{\ell}$, is asymptotically tight.

3. (iii)

   We give improved arboricity-sensitive running times for counting and/or detection of copies of $K_{\ell}$, for small $\ell\geq 4$ (Section 4). A key ingredient in our algorithms is the algorithm of Chiba and Nishizeki. Our new algorithms beat all previous algorithms in certain high-range arboricity intervals for every $\ell\geq 7$. We also provide up-to-date running times based on rectangular matrix multiplication times.

Let $G=(V,E)$ be an undirected graph. The neighborhood of a vertex $v\in V$ is the set $N(v)=\{w\ :\ (v,w)\in E\}$ of all adjacent vertices, and its cardinality $\deg(v)=|N(v)|$ is called the degree of $v$ in $G$. A clique in a graph $G=(V,E)$ is a subset $C\subset V$ of vertices, each pair of which is connected by an edge in $E$. The Clique problem is to find a clique of maximum size in $G$. An independent set of a graph $G=(V,E)$ is a subset $I\subset V$ of vertices such that no two of them are adjacent in $G$.

Unless specified otherwise: (i) all algorithms discussed are assumed to be deterministic; (ii) all graphs mentioned are undirected; (iii) all logarithms are in base $2$.

It should be noted that the asymptotically fastest algorithms for matrix multiplication have mainly a theoretical importance and are otherwise largely impractical [24, Ch. 10.2.4]. As such, any algorithm that employs fast matrix multiplication (FMM) inherits this undesirable feature. Whereas the notion of “combinatorial” algorithm does not have a formal or precise definition, such an algorithm is usually simpler to implement and practically efficient, see [35]. Combinatorial algorithms are sometimes theoretically less efficient than non-combinatorial ones but practically more efficient since they tend to be simpler to implement.

For a graph $G$, its arboricity $\alpha(G)$ is the minimum number of edge-disjoint forests into which $G$ can be decomposed [6]. For instance, it is known and easy to show that $\alpha(K_{n})=\lceil n/2\rceil$. A characterization of arboricity is provided by the following classic result [26, 27, 34]; see also [9, p. 60].

The degeneracy $d(G)$ of an undirected graph $G$ is the smallest number $d$ for which there exists an acyclic orientation of $G$ in which all the out-degrees are at most $d$. The degeneracy of a graph is linearly related to its arboricity, i.e., $\alpha(G)=\Theta(d(G))$; more precisely $\alpha(G)\leq d(G)\leq 2\alpha(G)-1$; see [3, 13, 23, 39].

It is worth noting that high arboricity is not an indication for the graph having many (or any) triangles. Indeed, the complete bipartite graph $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, or any of its dense subgraphs has arboricity $\Theta(n)$ but no triangles.

The algorithm solves the detection (or counting) problem for a complete subgraph $K_{\ell}$. Let $T(n,m,\ell)$ denote the running time of the algorithm for a graph with $n$ vertices and $m$ edges. Write $\ell=\ell_{1}+\ell_{2}$, for a suitable choice $\ell_{1},\ell_{2}\geq 2$. At the beginning, we run the algorithm of Chiba and Nishizeki to form a list of subgraphs isomorphic to $K_{\ell_{1}}$. Then, for each subgraph $G_{1}=(V_{1},E_{1})$ on the list: (i) we construct the subgraph $G_{2}$ of $G$ induced by vertices in $V\setminus V_{1}$ that are adjacent to all vertices in $V_{1}$; and (ii) we count the subgraphs isomorphic to $K_{\ell_{2}}$ in $G_{2}$ (or find one such subgraph); this is a (possibly recursive) call of the same procedure on a smaller instance. In other words, we count the number of extensions of the subgraph isomorphic to $K_{\ell_{1}}$ to a $K_{\ell}$. Another formulation of this method can be found in [21].

There are $O(\alpha^{\ell_{1}-2}\cdot m)$ copies of $K_{\ell_{1}}$ and they can be found in $O(\alpha^{\ell_{1}-2}\cdot m)$ time. For each fixed copy of $K_{\ell_{1}}$, the time spent in $G_{2}$ is at most $T(n,m,\ell_{2})$, and so the overall time satisfies the recurrence

Each copy of $K_{\ell}$ is generated exactly ${\ell\choose\ell_{1}}$ times and so the total count needs to be divided by this number in the end.

The algorithm solves the detection (or counting) problem for a complete subgraph $K_{\ell}$. Nešetřil and Poljak [28] showed an efficient reduction of detecting and counting copies of any complete subgraph to the aforementioned method of Itai and Rodeh [16] for triangle detection and counting. To start with, consider the detection of complete subgraphs of size $\ell=3j$. For a given graph $G$ with $n$ vertices, construct an auxiliary graph $H$ with $O(n^{j})$ vertices, where each vertex of $H$ is a complete subgraph of order $j$ in $G$. Two vertices $V_{1},V_{2}$ in $H$ are connected by an edge if $V_{1}\cap V_{2}=\emptyset$ and all edges in $V_{1}\times V_{2}$ are present in $G$; equivalently, $V_{1}\cup V_{2}$ is a complete subgraph on $|V_{1}|+|V_{2}|$ vertices. The detection (or counting) of triangles in $H$ yields an algorithm for the detection (or counting) of $K_{\ell}$’s in $G$, running in $O(n^{j\omega})$ time. For detecting complete subgraphs of size $\ell=3j+i$, where $i\in\{1,2\}$, the algorithm can be adapted so that it runs in $O(n^{j\omega+i})$ time.

The triangle method can be extended to larger subgraphs, i.e., if $\ell=kj+i$, for some $k\geq 4$, and $i\in\{0,1,\ldots,k-1\}$, the algorithm tries to detect a $K_{k}$ in $H$; see also [21]. We give a few applications at the end of this section.

Here we focus on $k=3$. For convenience, define the following integer functions

With this notation, the algorithm runs in $O(n^{\gamma(\ell)})$ time. Two decades later, Eisenbrand and Grandoni [12] refined the triangle method by using fast algorithms for rectangular matrix multiplication instead of those for square matrix multiplication. It partitions the graph intro three parts roughly of the same size: $\ell_{1}=\lfloor\ell/3\rfloor$, $\ell_{2}=\lceil(\ell-1)/3\rceil$, $\ell_{3}=\lceil\ell/3\rceil$. The refined algorithm runs in time $O(n^{\beta(\ell)})$ time. If the rectangular matrix multiplication is carried out via the straightforward partition into square blocks and fast square matrix multiplication (see, e.g., [8, Exercise 4.2-6]), one recovers the time complexity of the algorithm of Nešetřil and Poljak; that is, $\beta(\ell)\leq\gamma(\ell)$, see [12] for details. Eisenbrand and Grandoni [12] showed that the above inequality is strict for a certain range: if $\ell\pmod{3}=1$ and $\ell\leq 16$, or $\ell\pmod{3}=2$. In summary, their algorithm is faster than that of Nešetřil and Poljak in these cases. We subsequently refer to their method as the refined triangle method. Another extension of the triangle method is considered in [21].

The authors asked [18] whether there is an $O(m^{\ell\omega/6})$ algorithm for deciding whether a graph contains a $K_{\ell}$, if $\ell$ is a multiple of $3$. Eisenbrand and Grandoni showed that this is true for every multiple of $3$ at least $6$. Indeed, by their Theorem 2 [12], this task can be accomplished in time $O(m^{\beta(\ell)/2})$ for every $\ell\geq 6$, with $\beta(\ell)$ as in (3). If $\ell=3j$, where $j\geq 2$, then

It follows that the running time is $O(m^{\beta(\ell)/2})=O(m^{j\omega/2})=O(m^{\ell\omega/6})$. The proof of the theorem is rather involved. Here we provide an alternative simpler argument that also yields an arboricity-sensitive bound, item (i) below.

We first consider the general cases: (i) $\ell=3j$, $j\geq 3$; (ii) $\ell=3j+1$, $j\geq 2$; and (iii) $\ell=3j+2$, $j\geq 2$. It will be evident that our algorithms provide improved bounds for every $\ell\geq 7$. For a given $j\geq 2$, we shall consider the interval

1. (i)

   $\ell=3j$, $j\geq 3$. We use the triangle method with a refined calculation. The vertices of the auxiliary graph $H$ are subgraphs isomorphic to $K_{j}$. By the result of Chiba and Nishizeki [6], $H$ has $O(\alpha^{j-2}\cdot m)$ vertices. The algorithm counts triangles in $H$ in time proportional to

   $$\left(\alpha^{j-2}\cdot m\right)^{\omega}=\alpha^{(j-2)\omega}\cdot m^{\omega}.$$

   For $\ell=9,12,15$ (the entries in Table 1), these runtimes are $O(\alpha^{\omega}\cdot m^{\omega})$, $O(\alpha^{2\omega}\cdot m^{\omega})$, and $O(\alpha^{3\omega}\cdot m^{\omega})$, respectively.

   Since $\alpha=O(m^{1/2})$, the above expression is bounded from above as follows:

   $$\alpha^{(j-2)\omega}\cdot m^{\omega}=O\left(\left(m^{(j-2)/2}\cdot m\right)^{\omega}\right)=O\left(m^{j\omega/2}\right)=O\left(m^{\ell\omega/6}\right).$$

   Next, we show that for a certain high-range of $\alpha$, the new bound $\alpha^{(j-2)\omega}\cdot m^{\omega}$ beats all previous bounds, namely $m^{j\omega/2}$ and $\alpha^{3j-2}\cdot m$, for $j\geq 3$ (or $\ell=9,12,15,\ldots$). Let $\alpha=\Theta(m^{x})$, where $x\in I_{j}$. We first verify that

   $\displaystyle\alpha^{(j-2)\omega}\cdot m^{\omega}\ll m^{j\omega/2},\text{ or }((j-2)x+1)\omega<j\omega/2,$

   which holds for $x<1/2$. Secondly, we verify that

   	$\displaystyle\alpha^{(j-2)\omega}\cdot m^{\omega}$	$\displaystyle\ll\alpha^{3j-2}\cdot m,\text{ or }((j-2)x+1)\omega<(3j-2)x+1,\text{ or }$
   	$\displaystyle x$	$\displaystyle>\frac{\omega-1}{j(3-\omega)+2(\omega-1)},$

   which holds by the choice of the interval $I_{j}$. In particular, for $\ell=9$, this occurs for $x\in\left(\frac{\omega-1}{7-\omega},\frac{1}{2}\right)\supset(0.297,0.5)$; for $\ell=12$, this occurs for $x\in\left(\frac{\omega-1}{10-2\omega},\frac{1}{2}\right)\supset(0.262,0.5)$; for $\ell=15$, this occurs for $x\in\left(\frac{\omega-1}{13-3\omega},\frac{1}{2}\right)\supset(0.234,0.5)$. Moreover, if $\omega=2$, as conjectured, these intervals extend to $(1/5,1/2)$, $(1/6,1/2)$, and $(1/7,1/2)$, respectively.

2. (ii)

   $\ell=3j+1$, $j\geq 2$. The refined triangle method [12] with $\ell_{1}=j$, $\ell_{2}=j+1$, $\ell_{3}=j$, leads to rectangular matrix multiplication $[O(\alpha^{j-2}m)\times O(\alpha^{j-1}m)]\cdot[O(\alpha^{j-1}m)\times O(\alpha^{j-2}m)]$. Its complexity is at most $O(\alpha)$ times that of the square matrix multiplication with dimension $\alpha^{j-2}m$, the latter of which is $O(\alpha^{(j-2)\omega}\cdot m^{\omega})$. It follows that

   $$T(n,m,\ell)=O(\alpha\cdot\alpha^{(j-2)\omega}\cdot m^{\omega})=O(\alpha^{(j-2)\omega+1}\cdot m^{\omega}).$$

   For $\ell=7,10,13,16$ (the entries in Table 1), these runtimes are $O(\alpha\cdot m^{\omega})$, $O(\alpha^{\omega+1}\cdot m^{\omega})$, $O(\alpha^{2\omega+1}\cdot m^{\omega})$, and $O(\alpha^{3\omega+1}\cdot m^{\omega})$, respectively.

   As before, we show that for a certain high-range of $\alpha$, the new bound $\alpha^{(j-2)\omega+1}\cdot m^{\omega}$ beats all previous bounds, namely $m^{(j\omega+1)/2}$ and $\alpha^{3j-1}\cdot m$, for $j\geq 2$ (or $\ell=7,10,13,\ldots$). Let $\alpha=\Theta(m^{x})$, where $x\in I_{j}$. We first verify that

   $\displaystyle\alpha^{(j-2)\omega+1}\cdot m^{\omega}\ll m^{(j\omega+1)/2},\text{ or }((j-2)x+1)\omega<j\omega/2,$

   which holds for $x<1/2$. Secondly, we verify that

   	$\displaystyle\alpha^{(j-2)\omega+1}\cdot m^{\omega}$	$\displaystyle\ll\alpha^{3j-1}\cdot m,\text{ or }((j-2)x+1)\omega+x<(3j-1)x+1,\text{ or }$
   	$\displaystyle x$	$\displaystyle>\frac{\omega-1}{j(3-\omega)+2(\omega-1)},$

   which holds by the choice of the interval $I_{j}$. In particular, for $\ell=7$, this occurs for $x\in\left(\frac{\omega-1}{4},\frac{1}{2}\right)\supset(0.344,0.5)$; for $\ell=10$, this occurs for $x\in\left(\frac{\omega-1}{7-\omega},\frac{1}{2}\right)\supset(0.297,0.5)$; for $\ell=13$, this occurs for $x\in\left(\frac{\omega-1}{10-2\omega},\frac{1}{2}\right)\supset(0.262,0.5)$. Moreover, if $\omega=2$, as conjectured, these intervals extend to $(1/4,1/2)$, $(1/5,1/2)$, and $(1/6,1/2)$, respectively.

3. (iii)

   $\ell=3j+2$, $j\geq 2$. The refined triangle method [12] with $\ell_{1}=j+1$, $\ell_{2}=j$, $\ell_{3}=j+1$, leads to rectangular matrix multiplication $[O(\alpha^{j-1}m)\times O(\alpha^{j-2}m)]\cdot[O(\alpha^{j-2}m)\times O(\alpha^{j-1}m)]$. Its complexity is at most $O(\alpha^{2})$ times that of the square matrix multiplication with dimension $\alpha^{j-2}m$, the latter of which is $O(\alpha^{(j-2)\omega}\cdot m^{\omega})$. It follows that

   $$T(n,m,\ell)=O(\alpha^{2}\cdot\alpha^{(j-2)\omega}\cdot m^{\omega})=O(\alpha^{(j-2)\omega+2}\cdot m^{\omega}).$$

   For $\ell=8,11,14$ (the entries in Table 1), these runtimes are $O(\alpha^{2}\cdot m^{\omega})$, $O(\alpha^{\omega+2}\cdot m^{\omega})$, and $O(\alpha^{2\omega+2}\cdot m^{\omega})$, respectively.

   As before, we show that for a certain high-range of $\alpha$, this bound beats all previous bounds, namely $m^{(j\omega+2)/2}$ and $\alpha^{3j}\cdot m$, for $j\geq 2$ (or $\ell=8,11,14,\ldots$). Let $\alpha=\Theta(m^{x})$, where $x\in I_{j}$. We first verify that

   $\displaystyle\alpha^{(j-2)\omega+2}\cdot m^{\omega}\ll m^{(j\omega+2)/2},\text{ or }((j-2)x+1)\omega<j\omega/2,$

   which holds for $x<1/2$. Secondly, we verify that

   	$\displaystyle\alpha^{(j-2)\omega+2}\cdot m^{\omega}$	$\displaystyle\ll\alpha^{3j}\cdot m,\text{ or }((j-2)x+1)\omega+2x<3jx+1,\text{ or }$
   	$\displaystyle x$	$\displaystyle>\frac{\omega-1}{j(3-\omega)+2(\omega-1)},$

   which holds by the choice of the interval $I_{j}$. In particular, for $\ell=8$, this occurs for $x\in\left(\frac{\omega-1}{4},\frac{1}{2}\right)\supset(0.344,0.5)$; for $\ell=11$, this occurs for $x\in\left(\frac{\omega-1}{7-\omega},\frac{1}{2}\right)\supset(0.297,0.5)$; for $\ell=14$, this occurs for $x\in\left(\frac{\omega-1}{10-2\omega},\frac{1}{2}\right)\supset(0.262,0.5)$. Moreover, if $\omega=2$, as conjectured, these intervals extend to $(1/4,1/2)$, $(1/5,1/2)$, and $(1/6,1/2)$, respectively.

   The bound for $\ell=8$, $O(\alpha^{2}\cdot m^{\omega})$, is superseded by the bound $O\left(\alpha^{\omega+1}m^{\frac{\omega+1}{2}}\right)$, using another (so-called “the edge count”) method.

The previous general case derivations together with the instantiations below yield the running times listed in Table 1.