Listing $6$-Cycles in Sparse Graphs

Listing copies of a small pattern graph that occur as subgraphs of a host graph is a fundamental problem in algorithmic graph theory. In this work, we consider the problem of listing $C_{2k}$’s (i.e., $2k$-cycles) for fixed constant $k\geq 2$. Some examples of applications of $C_{2k}$ listing include analyzing social networks [motivationSocial], and understanding causal relationships in biological interaction graphs [motivationBIO]. (See e.g. [dense_cycle_detection_YZ] for further motivation.) In the following discussion we consider an $n$ vertex $m$ edge graph $G$ with $t$ $C_{2k}$’s (where $k\geq 2$ will be clear from context and $t$ is not necessarily known).

The main reason for focusing on even length cycles is that while there are dense graphs that contain no odd cycles (e.g. bipartite graphs), a classic result of Bondy and Simonovits [evenextremal] states that any graph with at least $100kn^{1+1/k}$ edges contains a $C_{2k}$, for any integer $k\geq 2$. This fact enables efficient “combinatorial” algorithms for $C_{2k}$ detection, in contrast to the case of odd length cycles where efficient $C_{2k+1}$ detection algorithms are based on matrix multiplication. In fact, very simple reductions (e.g. [vthesis]) show that for any $k\geq 1$, $C_{2k+1}$ detection is at least as hard as triangle detection, and the latter problem is known to be fine-grained subcubically equivalent to Boolean Matrix Multiplication [focsy]. Thus, fast algorithms for odd cycles cannot avoid matrix multiplication. We focus on even cycles from now on.

A classic result of Yuster and Zwick [dense_cycle_detection_YZ] shows how to determine whether a graph contains a $C_{2k}$ in $O(n^{2})$ time for any given constant $k\geq 2$. This quadratic running time is conjectured to be optimal in general (see [short_cycle_removal, LincolnVyas, Kn17], also discussed below); in particular, [short_cycle_removal] gave concrete evidence for the hardness of $C_{4}$ detection.

Nevertheless, in the regime of sparser graphs, where $m<o(n^{1+1/k})$ improvements are possible. For $C_{4}$’s there is a simple $O(m^{4/3})$ algorithm [alon1997finding] that matches the performance of the $O(n^{2})$ algorithm of [dense_cycle_detection_YZ] for $m=\Theta(n^{3/2})$, and improves on the performance for all $m<o(n^{3/2})$. Dahlgaard, Knudsen and Stöckel [Kn17] give an algorithm for $C_{2k}$ detection with running time $O(m^{2k/(k+1)})$ for every constant $k\geq 2$. This matches the $O(n^{2})$ running time from [dense_cycle_detection_YZ] for $m=\Theta(n^{1+1/k})$ and improves on it for $m<o(n^{1+1/k})$.

In fine-grained complexity, it is common to assume widely-believed hypotheses and use reductions to obtain conditional lower bounds for fundamental problems. For the special case of cycle detection problems, most conditional lower bounds are based on hypotheses related to triangle detection. One of the most common hypotheses is that triangle detection in $n$-node graphs does not have a “combinatorial” ¹¹1The class of combinatorial algorithms is not well defined, but intuitively refers to algorithms that do not use fast matrix multiplication as a subroutine. $O(n^{3-\varepsilon})$ time algorithm for $\varepsilon>0$ (in the word-RAM model). Vassilevska W. and Williams [focsy] showed that this hypothesis is equivalent to the so called BMM Hypothesis that postulates that there is no $O(n^{3-\varepsilon})$ time combinatorial algorithm for multiplying two $n\times n$ Boolean matrices.

As mentioned earlier, it is easy to show that under the BMM hypothesis, detecting any odd cycle $C_{2k+1}$ requires $n^{3-o(1)}$ time. Dahlgaard, Knudsen and Stöckel [Kn17] gave lower bounds for combinatorial detection of even cycles of fixed length in sparse graphs. They show that there is no combinatorial algorithm for $C_{6}$ detection, or $C_{2k}$ detection for any $k>4$, with running time $O(m^{3/2-\varepsilon})$ for $\varepsilon>0$. Lincoln and Vyas [LincolnVyas] give a similar conditional lower bound under a different hypothesis, extending the lower bounds for potentially non-combinatorial algorithms. Lincoln and Vyas show that, for large enough constant $k$, a $C_{2k}$ detection algorithm in graphs with $m\leq O(n)$ with running time $m^{3/2-\varepsilon}$ would imply an algorithm for $\max$-3-SAT with running time $2^{(1-\varepsilon^{\prime})n}n^{O(1)}$.

The problem of listing even cycles is less well-understood. Without improving the $C_{2k}$ detection algorithms discussed above, the best result that we could hope for in general is an algorithm with running time $O(n^{2}+t)$, where $t$ is the number of $2k$-cycles in the graph, and $O(m^{2k/(k+1)}+t)$ in the sparse setting where $m<o(n^{1+1/k})$. Recently, [Ab22] and [3sumLBCe] gave such an algorithm for $C_{4}$ listing. In fact, Jin and Xu’s [3sumLBCe] algorithm gives a stronger guarantee: After $O(m^{4/3})$ pre-processing time, they can (deterministically) enumerate $4$-cycles with $O(1)$ delay per cycle. Jin and Xu [3sumLBCe] (and concurrently by Abboud, Bringmann, and Fischer [3sumLBAmir]) shows that, under the 3SUM Hypothesis, there is no algorithm for $C_{4}$ enumeration with $O(n^{2-\varepsilon})$ or $O(m^{4/3-\varepsilon})$ pre-processing time and $n^{o(1)}$ delay, for $\varepsilon>0$.

For $C_{6}$’s, Jin, Zhou and Vassilevska Williams [C6sCe] give an $\widetilde{O}(n^{2}+t)$ listing algorithm. For sparse listing algorithms, the previous state of the art is [alon1997finding] whose work implies an $O(m^{(2k-1)/k}+t)$ time $C_{2k}$ listing algorithm. See also [bringmannclass] where the complexity of the harder problem of listing $H$-partite²²2A $k$-node $H$ is an $H$-partite subgraph of a $k$-partite graph $G$ with vertex set $V=\cup_{a\in V(H)}V_{a}$ if there are $k$ vertices $v_{1},\ldots,v_{k}$ such that $v_{a}\in V_{a}$ for each $a\in\{1,\ldots,k\}$ and the mapping $a\rightarrow v_{a}$ is an isomorphism between $H$ and the subgraph of $G$ induced by $v_{1},\ldots,v_{k}$. In other words, instead of looking for an arbitrary subgraph of $G$ isomorphic to $H$, one only focuses on the subgraphs with exactly one node in each $V_{a}$ and such that the node picked from $V_{a}$ corresponds to node $a$ of $H$. subgraphs is investigated.