Listing Even Cycles Faster than the Submodular-Width Barrier
May 28, 2026
Abstract
A classic result of Alon, Yuster, and Zwick (AYZ, Algorithmica 1997) shows that all \(2k\)-cycles in an \(m\)-edge (directed or undirected) graph can be listed in \(\tilde{O}(m^{2-1/k} + t)\) time, where \(t\) is the output size. This bound is a starting point for the notion of submodular width due to Marx (JACM, 2013), and then the PANDA framework by Abo Khamis, Ngo, and Suciu (PODS, 2017), which generalize the AYZ result to arbitrary conjunctive queries and input degree constraints. A central open question is whether combinatorial algorithms can beat the submodular-width barrier.
Bringmann and Gorbachev (STOC 2025) gave lower-bound evidence that submodular width may be optimal for general conjunctive queries under combinatorial algorithms. The picture changes, however, for \(2k\)-cycles on undirected graphs, whose corresponding queries have self-joins and symmetric input EDBs: recent works have improved on AYZ for even-cycle detection and listing. Pinning down the complexity of \(C_{2k}\)-detection and listing is thus a natural step toward overcoming the submodular-width barrier for queries with self-joins or symmetric EDBs.
With respect to the detection problem (a Boolean conjunctive query), Dahlgaard, Knudsen, and Stöckel (STOC 2017) showed that \(C_{2k}\)-detection can be solved in \(\tilde{O}(m^{2k/(k+1)})\) time, improving on the AYZ bound. The even-cycle listing problem (a full conjunctive query) is more challenging. Recent works have made progress on small cycles. Jin and Xu (STOC 2023) (and independently Abboud, Khoury, Leibowitz, and Safier, FSTTCS 2023) showed that 4-cycles can be listed in \(\tilde{O}(m^{4/3}+t)\) time, and Vassilevska Williams and Westover (ITCS 2025) showed that 6-cycles can be listed in \(\tilde{O}(m^{8/5}+t)\) time; both results improve the corresponding AYZ bounds of \(\tilde{O}(m^{3/2})\) and \(\tilde{O}(m^{5/3})\), respectively. The general case, however, has remained open since the original AYZ paper some 30 years ago.
In this paper, building on the works of Dahlgaard, Knudsen, and Stöckel, and of Vassilevska Williams and Westover, we prove that \(2k\)-cycles can be listed in \(\tilde{O}\left(m^{(2k^2-k+1)/(k^2+1)}+t\right)\) time, improving the AYZ bound for every \(k \geq 3\). The key technical ingredient is an asymmetric supersaturation result for even cycles. Additionally, our algorithms are expressed entirely in terms of join and project operators over multiple tree-decomposition query plans, making them naturally amenable to efficient implementation in database systems. This is in contrast to the breadth-first search (BFS)-based approaches in the prior graph algorithms literature.
1 Introduction↩︎
Conjunctive query (CQ) evaluation is a fundamental problem across many areas, including algorithmic graph theory, relational database management, constraint satisfaction, and logic programming [1]–[5]. There is a natural synergy between graph algorithms and query evaluation. In particular, a graph is simply a binary relation, and subgraph pattern queries can naturally be expressed as CQs; thus, advances in graph algorithms have often translated directly into progress on query evaluation, and vice versa.
For example, a special case of conjunctive query evaluation is the problem of finding or listing a small (hyper)graph pattern inside a large graph. A long line of work on this problem [3], [6]–[12] led to the AGM-bound [12] for the worst-case output size of conjunctive queries, and the notion of worst-case optimal join algorithms [13]–[16] for evaluating CQs in time proportional to the worst-case output size.
Another example that is central to our story is the classic result of Alon, Yuster, and Zwick [17]: given any (directed or undirected) graph with \(m\) edges and a constant \(k\), one can detect whether a \(k\)-cycle exists in time \(\widetilde{O}(m^{2-1/\lceil k/2 \rceil})\), and list all \(k\)-cycles in time \(\widetilde{O}(m^{2-1/\lceil k/2 \rceil} + t)\), where \(t\) is the number of \(k\)-cycles. Marx [18] introduced the notion of submodular width of a conjunctive query; the PANDA framework [5] later extended this to a general algorithm that evaluates any conjunctive query \(Q\) over a database of size \(N\) in time \(\widetilde{O}(N^{\mathsf{subw}(Q)} + t)\), where \(\mathsf{subw}(Q)\) is the submodular width of \(Q\) and \(t\) is the output size. The submodular width of the \(k\)-cycle query is \(2-1/\lceil k/2 \rceil\), and thus we recover the AYZ result as a special case.
There is some evidence that the submodular width may be the best one can hope for in general, amongst “combinatorial algorithms”. In particular, Bringmann and Gorbachev [19] recently proved that for the class of so-called sub-quadratic graph patterns — of which cycles are a special case — the submodular-width runtime is indeed optimal, assuming the MinClique [20], 3SUM [21], or ZeroClique [22] hypotheses.
Before proceeding, it is worth clarifying precisely what we mean by a \(k\)-cycle query. Let \(E\) be the edge relation of a (directed or undirected) graph, and an integer constant \(k\geq 2\). The \(k\)-cycle detection query is the Boolean conjunctive query \[\begin{align} C_k() \leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{k-1},v_k) \wedge E(v_k,v_1) \wedge \bigwedge_{i \neq j} v_i \neq v_j, \label{eqn:ck:detection} \end{align}\tag{1}\] and the \(k\)-cycle listing query outputs the cycles: \[\begin{align} C_k(v_1,\ldots,v_k) \leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{k-1},v_k) \wedge E(v_k,v_1) \wedge \bigwedge_{i \neq j} v_i \neq v_j. \label{eqn:ck:listing} \end{align}\tag{2}\] These are crucially different from the \(k\)-closed-walk queries, which drop the distinctness constraints: \[\begin{align} W_k() &\leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{k-1},v_k) \wedge E(v_k,v_1), \tag{3} \\ W_k(v_1,\ldots,v_k) &\leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{k-1},v_k) \wedge E(v_k,v_1). \tag{4} \end{align}\] The closed-walk queries are standard CQs and fall directly within the scope of the PANDA framework, whereas the cycle queries require handling the \(\neq\) constraints, which are harder to deal with. In particular, variables in the cycle queries are fully connected into a clique, which means there is no non-trivial tree decomposition. Applying an algorithm such as PANDA to the cycle queries amounts to brute-force search over all \(k\)-tuples of vertices, which takes \(O(n^k)\) time. We will explain in Section 2 how the color-coding technique of Alon, Yuster, and Zwick [23] can be used to handle the \(\neq\) constraints via Boolean tensor decomposition [24]. In particular, the submodular width of the \(k\)-closed-walk queries is \(2-1/\lceil k/2 \rceil\); together with the color-coding technique, this lets us evaluate the \(k\)-cycle queries in the time predicted by the submodular width.
A key open question in algorithmic graph theory over the past 30 years has been to beat the runtime of the AYZ algorithm. Recently, there has been some progress on the \(C_{2k}\) detection and listing problems in undirected graphs. Before describing this progress, it is worth clarifying upfront how “beating the AYZ runtime” is possible at all in light of the recent fine-grained lower bound of Bringmann and Gorbachev [19], which matches the AYZ exponent. Their bound applies to the colored variant of cycle listing, in which the host graph’s vertex set \(V\) is partitioned into \(2k\) classes and each of the \(2k\) atoms of the cycle query is governed by its own bipartite relation \(E_1, \dots, E_{2k}\) between consecutive classes — these \(2k\) relations may be chosen independently and adversarially. Our setting is strictly more restricted: all \(2k\) atoms refer to a single shared edge relation \(E\), and \(E\) is symmetric because the host graph is undirected. Both restrictions matter — the shared-relation property already rules out the adversarial 3SUM-style gadgets of [19], and symmetry of \(E\) is what enables the supersaturation tools that our algorithm is built on.
On the detection side, Yuster and Zwick [25] showed how to detect a \(2k\)-cycle in \(O(n^2)\)-time for all \(k\), where \(n\) is the number of vertices of the graph. In the dense regime, this is believed to be the best possible. In the sparse regime, Dahlgaard, Knudsen, and Stöckel [26] showed how to detect a \(2k\)-cycle in an undirected graph in time \(O(m^{2k/(k+1)})\), improving on the AYZ bound for all \(k\). Lincoln and Vyas [27] showed that, when \(k\) is odd, this exponent is optimal under some standard hypotheses. Dahlgaard et al. introduced the so-called \(\Phi\)-norm of a vector and a matrix, which is then used to bound the number of capped \(k\)-walks in a \(C_{2k}\)-free graph. Their technique is a key building block for our results, and we will explain it in more detail in Section 2.
On the listing side, Jin and Xu [28] (and independently Abboud, Khoury, Leibowitz, and Safier [29]) showed how to list all \(4\)-cycles in time \(\tilde{O}(m^{4/3}+t)\), and Vassilevska Williams and Westover [30] devised an algorithm to list all \(6\)-cycles in time \(\tilde{O}(m^{8/5}+t)\). Both runtimes improve upon the corresponding AYZ bounds of \(\tilde{O}(m^{3/2})\) and \(\tilde{O}(m^{5/3})\), respectively. They also proved a conditional lower bound showing that \(\tilde{O}(m^{4/3-\epsilon} + t)\) time is not possible for listing \(4\)-cycles. In the dense-graph regime, an \(\tilde{O}(n^2+t)\)-time algorithm is known only for listing \(4\)-cycles [28] and \(6\)-cycles [31]. A natural open question is therefore to design an algorithm that beats the AYZ bound for listing \(2k\)-cycles for all \(k\).
One of the reasons researchers have focused on the even-cycle case is the existence of a Turán-type theorem [32] and supersaturation results [33] for even cycles.1 In particular, a classic theorem of Bondy and Simonovits [34] states that any graph with \(m = \Omega(k n^{1+1/k})\) edges must contain a \(2k\)-cycle. Using this result, Dahlgaard et al. [26] showed that a \(C_{2k}\)-free graph must have a “small” number of capped \(k\)-walks. We will define this notion precisely in Section 2. At a high level, this structural result bounds the bag size of a tree decomposition used to answer the \(C_{2k}\) query, which is what enables algorithms faster than AYZ. For the listing problem, however, a Turán-type theorem alone is not sufficient. What we need is a quantitative supersaturation result: a guarantee that a sufficiently dense graph contains not just one \(2k\)-cycle, but many — enough that we can charge the running time of our algorithm to the output size \(t\).
Given that the exponent \(2k/(k+1)\) is likely to be optimal for \(C_{2k}\) detection [27], it is natural to ask whether the same exponent works for \(C_{2k}\)-listing, i.e. whether we can list all \(2k\)-cycles in time \(\tilde{O}(m^{2k/(k+1)} + t)\). As shown in Vassilevska Williams and Westover [30] (attributed therein to Ce Jin and Renfei Zhou), we can list \(2k\)-cycles in time \(\tilde{O}(m^{2k/(k+1)} + t)\) if the following supersaturation conjecture holds, which is stated as Conjecture 25 in [30].
Conjecture 1. Let \(G = (A\cup B, E)\) be a bipartite graph with \(m\) edges. If \(m = \Omega\bigl(k\bigl(|A| + |B| + (|A||B|)^{(k+1)/2k}\bigr)\bigr)\), then the number \(t\) of \(2k\)-cycles in \(G\) satisfies \(t \;\geq\; \Omega\!\left(\frac{m^{2k}}{|A|^k |B|^k}\right).\)
For \(k=2\) the conjecture can be proved using elementary arguments, as we shall illustrate in Section 3. For \(k=3\), Vassilevska Williams and Westover [30] made some progress towards the conjecture, thus obtaining an \(\widetilde{O}(m^{8/5} + t)\)-time algorithm for listing \(6\)-cycles in an undirected graph. This was the state of the art in even-cycle listing prior to our work.
Our contributions. Building on the work of Dahlgaard et al. [26] and Vassilevska Williams and Westover [30], we prove that all \(2k\)-cycles in an undirected graph can be listed in time \(O\!\left((m^{(2k^2-k+1)/(k^2+1)} + t)\log m\right)\) for all \(k \geq 2\). This is the first improvement to \(2k\)-cycle listing for all \(k \geq 3\) since the AYZ result 30 years ago. From a database perspective, our result indicates that queries with self-joins and symmetric input relations can be evaluated more efficiently than what the submodular width would predict, and that extremal and supersaturation results can be powerful tools for query evaluation.
The technical contributions are as follows. Using a supersaturation result of Jiang and Yepremyan [35], we prove a weaker form of Conjecture 1. We then exploit the capped-\(k\)-walk accounting framework of Dahlgaard et al. [26] to bound the \(\Phi\)-norm of the adjacency matrix of the graph, which in turn gives a tight bound on the number of capped \(k\)-walks. The final algorithm is expressed via Boolean tensor decomposition — capturing the color-coding technique of AYZ — where the query plan is a collection of tree decompositions whose bag sizes are controlled by the capped-\(k\)-walk bound. Along the way, our approach shaves a \(\log^{k+1} n\) factor from the layered decomposition approach of [30].
For \(k \geq 4\), our runtime strictly improves upon AYZ and is the first new result in this regime since the original paper. For \(k = 3\) (listing \(6\)-cycles), our exponent (\(8/5\)) matches that of Vassilevska Williams and Westover [30], but our algorithm improves upon theirs in several respects: (1) we avoid the \(O(\log^{74} n)\) polylogarithmic overhead present in their algorithm; (2) we require no computer-assisted case analysis (their proof involved approximately 576 cases); and (3) our query plan is expressed entirely using join and project operators, without BFS traversal, making it naturally amenable to implementation in database systems.
A further benefit is that our algorithm and its analysis are simple: the algorithm can be implemented via query rewriting, making it straightforward to deploy in practice. In addition to the obvious application of our result to efficiently evaluating the \(C_{2k}\) query in relational databases (and graph databases), we would also like to bring to the attention of database-theory researchers the idea of proving and applying extremal and supersaturation results to database query evaluation.
Outline. The rest of the paper is organized as follows. In Section 2, we introduce the necessary background and notations. In particular, we explain how color-coding can be used to reduce a cycle-query to a closed-walk query, and the \(\Phi\)-norm approach. In the “warm-up” Section 3, we illustrate the supersaturation phenomenon and how it can be used to show that Conjecture 1 implies an algorithm to list \(2k\)-cycles in time \(\tilde{O}(m^{2k/(k+1)}+t)\). This result was already shown in Vassilevska Williams and Westover [30], but our analysis is different, and more importantly, the algorithm is a database query plan that does not require BFS traversal. The section briefly presents a folklore result proving the conjecture for \(C_4\), which implies that \(4\)-cycles can be listed in time \(\tilde{O}(m^{4/3}+t)\). Section 4 presents our main result for listing \(2k\)-cycles for all \(k\). Finally, in Section 5, we conclude with some open questions and directions for future work.
2 Background↩︎
2.1 Tree decomposition and multiple query plans↩︎
A tree decomposition (TD) of a hypergraph \(\mathcal{H}=([n],\mathcal{E})\) is a pair \((T, \chi)\), where \(T=(V(T),E(T))\) is a tree and \(\chi: V(T) \to 2^{[n]}\) assigns to each node of \(T\) a set of vertices of \(\mathcal{H}\), called a bag, subject to two conditions: (i) every hyperedge \(S \in \mathcal{E}\) is contained in some bag \(\chi(b)\); and (ii) for every vertex \(v \in [n]\), the set of nodes \(\{b \in V(T) \mid v \in \chi(b)\}\) induces a connected subtree of \(T\).
Each conjunctive query (CQ) \(Q(F) \text{ :- } \bigwedge_{S \in \mathcal{E}} R_S(S)\) is naturally associated with a hypergraph \(\mathcal{H}= ([n], \mathcal{E})\), where \([n]\) is the set of variables of \(Q\), each hyperedge \(S \in \mathcal{E}\) is associated with an atom \(R_S(S)\), and \(F \subseteq [n]\) is the set of free variables. In this paper we are only concerned with Boolean conjunctive queries (i.e., \(F = \emptyset\)) and full conjunctive queries (i.e., \(F = [n]\)). A tree decomposition of \(Q\) is defined as a tree decomposition of its associated hypergraph \(\mathcal{H}\). We abuse notation and use \(S\) to refer to both the hyperedge in \(\mathcal{E}\) and the set of variables in the corresponding relation \(R_S\).
There is essentially only one tree decomposition for both the \(C_{2k}\)-detection and \(C_{2k}\)-listing queries 1 and 2 , consisting of a single bag \(\{v_1, v_2, \ldots, v_{2k}\}\) that contains all the variables. This is due to the \(\neq\) atoms that connect all the variables together into a clique. On the other hand, the \(W_{2k}\)-detection and \(W_{2k}\)-listing queries 3 and 4 have many non-trivial tree decompositions, as shown in Figure 1. In the figure, we omit the tree decompositions themselves and show only the structures of the bags. On the left, every triangle drawn is a bag and two bags are adjacent if they share an edge. On the right, we have a tree decomposition with two bags, one containing all variables on the top half of the cycle and the other containing all variables on the bottom half of the cycle.
A tree decomposition of a query represents a query plan [1], [3], [36]. Specifically, given a tree decomposition \((T, \chi)\) of \(W_{2k}\), for each node \(b \in V(T)\) we evaluate the restriction2 of \(W_{2k}\) to the variables in the bag \(\chi(b)\), yielding an intermediate relation \(I_{\chi(b)}\) over the variables \(\chi(b)\). The full query result can then be obtained by joining all the intermediate relations \(\{I_{\chi(b)}\}_{b \in V(T)}\) along the tree \(T\), following Yannakakis’s algorithm [36]. The runtime of this procedure is bounded by the size of the largest intermediate relation. In particular, if the query is a Boolean CQ, then the runtime is \(O(N+\max_{b \in V(T)} |I_{\chi(b)}|)\), and if the query is a full CQ (i.e., a listing query) then the runtime is \(O(N+\max_{b \in V(T)} |I_{\chi(b)}| + t)\), where \(N\) is the input size and \(t\) is the output size.
One of the fundamental ideas behind both the AYZ algorithm [17] and Marx’s submodular width [18] is that one can use multiple query plans for a single query, by partitioning the data appropriately and handling each partition with a different tree decomposition.
To illustrate, consider the \(W_{2k}\)-detection and listing queries. Let \(\Delta\) be a parameter to be fixed later. Partition the vertex set into heavy vertices (those of degree \(> \Delta\)) and light vertices (all others), denoted by \(V := H \cup L\). AYZ’s query plan rewrites the \(W_{2k}\) query as a disjunction of \(2k+1\) sub-queries, each of which can be answered by a different tree decomposition. In particular, for each \(i \in [2k]\), we have a sub-query \(W^{h,i}_{2k}\) that looks for a closed walk of length \(2k\) where the vertex \(v_i\) is heavy. Additionally, there is one more sub-query \(W^\ell_{2k}\) that looks for a closed walk of length \(2k\) where all vertices are light: \[\begin{align} W^{h,i}_{2k}(v_1,\dots,v_{2k}) &\leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{2k-1},v_{2k}) \wedge E(v_{2k},v_1) \wedge \underbrace{H(v_i)}_{\mathrm{heavy~vertex}} \\ W^\ell_{2k}(v_1,\dots,v_{2k}) &\leftarrow E(v_1,v_2) \wedge E(v_2,v_3) \wedge \cdots \wedge E(v_{2k-1},v_{2k}) \wedge E(v_{2k},v_1) \wedge \underbrace{\bigwedge_{j \in [2k]} L(v_j)}_{\mathrm{all~light~vertices}} \end{align}\] The first \(2k\) tree decompositions, shown on the left of Figure 1, handle the \(W^{h,i}_{2k}\) sub-queries. The remaining tree decomposition, shown on the right of Figure 1, handles the all-light case with two bags, one covering the top half and the other covering the bottom half of the walk.
For the heavy query plans, since there are at most \(O(m/\Delta)\) heavy vertices, every intermediate relation corresponding to a bag of such a plan has size at most \(O(m^2/\Delta)\). For the all-light query plan, each of the two bags is bounded in size by \(O(m \Delta^{k-1})\), since each light vertex has degree bounded by \(\Delta\). Choosing \(\Delta = m^{1/k}\) to balance the two bounds gives \(O(m^2/\Delta) = O(m \Delta^{k-1}) = O(m^{2-1/k})\), and AYZ achieves \(O(m^{2-1/k})\) time for \(W_{2k}\)-detection and \(O(m^{2-1/k} + t)\) time for \(W_{2k}\)-listing.
2.2 Color-coding and Boolean tensor decomposition↩︎
As noted above, the \(C_{2k}\) queries have only one (trivial) tree decomposition — a single bag containing all variables — making a direct application of the query-plan framework prohibitively expensive. The color-coding technique [23] overcomes this obstacle by effectively reducing the cycle query to a closed-walk query. This reduction can be done with query rewriting, using Boolean tensor decomposition [24] as follows.
The predicates that distinguish the \(C_{2k}\) query from the \(W_{2k}\) query are exactly the distinctness constraints: \(\bigwedge_{i \neq j} V(v_i) \wedge V(v_j) \wedge v_i \neq v_j,\) where \(V\) denotes the vertex set of the graph. Using color-coding, one can compute in linear time \(r \cdot 2k\) unary relations \(C_{\ell,i}\), for \(\ell \in [r]\) and \(i \in [2k]\), with \(r = 2^{O(k)} \log n\), such that \[\bigwedge_{i \neq j} V(v_i) \wedge V(v_j) \wedge v_i \neq v_j \;\equiv\; \bigvee_{\ell=1}^{r} \bigwedge_{i \in [2k]} C_{\ell,i}(v_i).\] (We do not need to materialize these unary relations, as they are defined by hash functions.) Substituting this into the \(C_{2k}\) query and distributing the disjunction reduces the cycle query to \(r\) instances of the closed-walk query \(W_{2k}\), each augmented with unary filters \(C_{\ell,i}\) on the variables: \[\begin{align} E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \underbrace{\bigwedge_{i \neq j} v_i \neq v_j}_{\mathrm{distinctness}} \equiv\;& E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \underbrace{\bigvee_{\ell \in [r]} \bigwedge_{i \in [2k]} C_{\ell,i}(v_i)}_{\text{every v_i has a ``color''}} \\ \equiv\;& \bigvee_{\ell \in [r]} \Bigl[E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \underbrace{\bigwedge_{i \in [2k]} C_{\ell,i}(v_i)}_{\mathrm{filtering~redistribution}}\Bigr]. \end{align}\]
Each such instance can then be answered using AYZ’s multi-TD query plan for closed walks, at a cost of \(O(m^{2-1/k})\) per instance. The total runtime for \(C_{2k}\)-detection is therefore \(\tilde{O}(m^{2-1/k})\), and for \(C_{2k}\)-listing it is \(\tilde{O}(m^{2-1/k} + t)\), recovering the AYZ bounds for even cycles. Here, \(\tilde{O}\) hides a \(2^{O(k)} \log n\) factor.
Remark 2. Here \(t\) counts cycles, not closed walks, so the listing algorithm is output-sensitive in the number of cycles. One cannot simply drop the distinctness constraints, enumerate all closed walks, and filter out the non-cycles: the number of closed walks can be far larger than the number of cycles, so this naive approach pays for walks rather than for cycles. A tree, for example, has no cycles but plenty of even-length closed walks.
2.3 Capped \(k\)-walks and the \(\Phi\)-norm↩︎
This section recasts the key ideas of Dahlgaard, Knudsen, and Stöckel [26] in the language of database queries and tree decompositions. Beyond being more familiar to database-theory readers, this view is also more directly implementable: it is not obvious how to realize the algorithms of [26] as typical database query plans.
The AYZ analysis in the previous section uses only a single tree decomposition for the all-light case (the right side of Figure 1). Dahlgaard, Knudsen, and Stöckel [26] made a sharp observation: because the graph is undirected, one can break an even cycle into two halves at the vertex \(v_i\) of highest degree on the cycle. This is analogous to the \(2k\) heavy TDs on the left of Figure 1, where we anchor at each position \(v_i\) for \(i \in [2k]\); the same anchoring strategy can be applied on the right side as well.
Specifically, given a graph \(G = (V, E)\), let \(V_p\) denote the set of vertices whose degree lies in the interval \((2^{p-1}, 2^p]\), for \(p = 0, 1, \ldots, \lceil \log \Delta \rceil\). Let \(\bar{V}_p := \bigcup_{q \leq p} V_q\) be the set of vertices of degree at most \(2^p\). We proceed as in the AYZ algorithm above, but handle the all-light data partition differently: we rewrite the all-light query as a disjunction of \(2k \cdot \lceil \log \Delta \rceil\) sub-queries: \[\begin{align} &E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \bigwedge_{i \in [2k]} L(v_i) \\ \equiv\;& E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \bigwedge_{i \in [2k]} L(v_i) \wedge \underbrace{\bigvee_{\substack{i \in [2k] \\ p \in [\lceil\log\Delta\rceil]}}\Bigl[V_p(v_i) \wedge \bigwedge_{j \neq i} \bar{V}_p(v_j)\Bigr]}_{\text{for some i, v_i is of highest degree}} \\ \equiv\;& \bigvee_{\substack{i \in [2k] \\ p \in [\lceil\log\Delta\rceil]}} \Bigl[E(v_1,v_2) \wedge \cdots \wedge E(v_{2k},v_1) \wedge \bigwedge_{i \in [2k]} L(v_i) \wedge \underbrace{V_p(v_i) \wedge \bigwedge_{j \neq i} \bar{V}_p(v_j)}_{v_i \text{ in the highest degree bucket}}\Bigr]. \end{align}\] We will use the TD on the right of Figure 1 to handle each of these sub-queries, where the vertices \(v_i\) and \(v_{i+k-1}\) (circularly) are anchored in the middle of the cycle and the two bags are split at \(v_i\) and \(v_{i+k-1}\). In graph-theoretic terms, each sub-query looks for cycles that pass through a vertex in \(V_p\) with all other vertices in \(\bar{V}_p\). It is clear that the union of the answers to these sub-queries equals the answer to the original query. The main task is then to bound the size of the intermediate relations produced by each of these tree decompositions.
For each such “light” TD anchored at position \(i\) and level \(p\), the bag size is bounded by the number of \(k\)-walks in \(G\) that start from a vertex in \(V_p\) and visit only vertices in \(\bar{V}_p\). We call these capped \(k\)-walks, and denote their total count by \(\kappa_k(G)\).
To bound \(\kappa_k(G)\), Dahlgaard et al. [26] introduced a powerful analytical instrument: the \(\Phi\)-norm.
Definition 3 (\(\Phi\)-norm). The \(\Phi\)-norm* of a vector \(\boldsymbol{v}\) is defined as \[\begin{align} \|\boldsymbol{v}\|_{\Phi} = \int_0^\infty \sqrt{|\{ i : |v_i| \geq x \}|} \, dx. \end{align}\] The \(\Phi\)-norm of a matrix \(\boldsymbol{A}\) is defined as the operator norm induced by the vector \(\Phi\)-norm: \[\begin{align} \|\boldsymbol{A}\|_{\Phi} = \sup_{\boldsymbol{v} \neq \boldsymbol{0}} \frac{\|\boldsymbol{A}\boldsymbol{v}\|_{\Phi}}{\|\boldsymbol{v}\|_{\Phi}}. \end{align}\]*
Throughout the paper, we write \(A \lesssim B\) to mean \(A = O(B)\). The following bound on \(\kappa_k(G)\) via the \(\Phi\)-norm can be inferred from the proof of Lemma 1.7 of [26].
Lemma 4 ([26]). Let \(\boldsymbol{A}_p\) denote the adjacency matrix of the subgraph of \(G\) induced on vertices in \(\bar{V}_p\) of degree at most \(\Delta\). Then, \[\begin{align} \kappa_k(G) \lesssim m \cdot (\max_{p} \, \|\boldsymbol{A}_p\|_{\Phi})^{k-1}. \end{align}\]
The \(\Phi\)-norm of a matrix can be bounded via the following “indicator” version:
Lemma 5 ([26]). Let \(\boldsymbol{A}\) be a real \(n \times n\) matrix. If, for all vectors \(\boldsymbol{v} \in \{0,1\}^n\) we have \(\|\boldsymbol{A}\boldsymbol{v}\|_{\Phi} \leq C \|\boldsymbol{v}\|_{\Phi}\) for some value \(C\), then \(\|\boldsymbol{A}\|_{\Phi} \leq 16C\).
3 Warm-ups↩︎
This section presents three warmup results that illustrate how Turán-type bounds and the more general supersaturation phenomenon enable efficient algorithms for \(2k\)-closed walks and \(2k\)-cycles on undirected graphs. We begin with a simple supersaturation result that lets us solve \(W_{2k}\)-detection in \(O(1)\) time and \(W_{2k}\)-listing in output-linear time. Then, we prove that Conjecture 1 implies a \(\tilde{O}(m^{2k/(k+1)}+t)\)-time algorithm for \(2k\)-cycle listing, matching the \(C_{2k}\)-detection exponent of Dahlgaard, Knudsen, and Stöckel [26]. This result was already established by Vassilevska Williams and Westover [30] (attributed to Jin and Xu); however, our analysis differs from theirs, and our algorithm — which avoids BFS traversal — is friendlier to database-system implementations. Finally, as an application of this result, we show that \(C_4\)-listing can be done in \(\tilde{O}(m^{4/3}+t)\) time by proving that the supersaturation conjecture holds for \(4\)-cycles. This fact is already known and is folklore.
3.1 The \(2k\)-closed walk queries↩︎
Proposition 6. Given an undirected graph \(G=(V,E)\) and an integer \(k \geq 2\), we can answer the Boolean \(W_{2k}\)-detection query in \(O(1)\) time and the \(W_{2k}\)-listing query in \(O(1+t)\) time, where \(t\) is the output size.
Proof. Since we can always walk back and forth on an edge, the \(W_{2k}\)-detection query is trivially true if \(G\) has at least one edge. This is a trivial example of a Turán-type theorem for \(2k\)-closed walks. Note that the reasoning does not work for odd-length closed walks.
Next, consider the listing version. Using the tree decomposition from the right of Figure 1, we can list \(2k\)-closed walks in time \(O(\text{\# k-walks} + t)\), as explained in Section 2.1. Thus, it is sufficient to prove that \(\text{\# k-walks} \leq t\).
Let \(\boldsymbol{A}\) be the adjacency matrix of \(G\) and \(\boldsymbol{1}\) be the all-\(1\) vector of dimension \(n\), where \(n\) is the number of vertices in \(G\). The number of \(k\)-walks in \(G\) is \(\boldsymbol{1}^\top \boldsymbol{A}^k \boldsymbol{1}\), and the number of \(2k\)-closed walks in \(G\) is \[\begin{align} t = \text{trace}(\boldsymbol{A}^{2k}) &= \text{trace}((\boldsymbol{A}^k)^\top \boldsymbol{A}^k) = \|\boldsymbol{A}^k\|_F^2 = \sum_{u,v} (\boldsymbol{A}^k)_{u,v}^2 \geq \sum_{u,v} (\boldsymbol{A}^k)_{u,v} = \boldsymbol{1}^\top \boldsymbol{A}^k \boldsymbol{1} = \text{\# k-walks}. \end{align}\] ◻
3.2 Why the supersaturation conjecture implies efficient \(2k\)-cycle listing↩︎
We now prove the implication. Our analysis differs from those in [26], [30], and so may be of independent interest.
Lemma 7. Suppose Conjecture 1 holds. Let \(\boldsymbol{A}\) be the adjacency matrix of a graph with maximum degree \(\Delta\), \(m\) edges, and \(t\) \(2k\)-cycles. Then, \(\|\boldsymbol{A}\|_\Phi = O(m^{1/(k+1)} + t^{1/(2k)}\log\Delta + \sqrt\Delta)\).
Proof. From Lemma 5, it is sufficient to show that, for any subset \(S\) of vertices, we have \(\|\boldsymbol{A}_S\|_\Phi = O(m^{1/(k+1)} + t^{1/(2k)}\log \Delta + \sqrt\Delta) \sqrt{|S|}\). Let \(\boldsymbol{1}_S\) denote the indicator vector of \(S\), let \(E(v,S)\) denote the set of edges between \(v\) and \(S\), and let \(E(B, S)\) denote the set of edges between the set of vertices \(B\) and \(S\). Define \[\begin{align} B(x) &:= \{ v : |E(v,S)| \geq x \} && f(x) := |B(x)| && s := |S| \end{align}\] Then, our goal is to bound \(\|\boldsymbol{A}\boldsymbol{1}_S\|_{\Phi} = \int_{x=0}^{\Delta} \sqrt{f(x)} \, dx\), subject to the constraints we know about \(f\). Since there are at most \(m\) edges in total, and since every vertex in \(S\) has degree at most \(\Delta\), we have \[\begin{align} x \cdot f(x) &\leq 2m && x \cdot f(x) \leq s\Delta && \forall x \leq \Delta. \label{eq:edge:count:constraint} \end{align}\tag{5}\]
Next, from Conjecture 1, there is a constant \(C\) (depending on \(k\)) such that \[\begin{align} x \cdot f(x) \leq |E(B(x),S)| \leq C(f(x) + s + (f(x)s)^{(k+1)/2k} + t^{1/2k} \sqrt{f(x)s}). \end{align}\] Thus, when \(x \geq 2C\) the following holds: \[\begin{align} \frac{x}{2} \cdot f(x) &\leq C(s + (f(x)s)^{(k+1)/2k} + t^{1/2k} \sqrt{f(x)s}) \\ &\leq 3C\max\bigl\{s, (f(x)s)^{(k+1)/2k}, t^{1/2k} \sqrt{f(x)s}\bigr\}. \end{align}\] As a consequence, when \(x \geq 2C\), one of the following three cases must hold:
\(x \cdot f(x) \leq 6Cs\), implying \(\sqrt{f(x)} \leq O(\sqrt{s/x})\).
\(x \cdot f(x) \leq 6C(f(x)s)^{(k+1)/2k}\), implying \(\sqrt{f(x)} \leq O(s^{(k+1)/(2(k-1))} / x^{k/(k-1)})\).
\(x \cdot f(x) \leq 6C t^{1/2k} \sqrt{f(x)s}\), implying \(\sqrt{f(x)} \leq O(t^{1/(2k)} \sqrt{s} / x)\).
Combining these with the trivial bound \(\sqrt{f(x)} = O(\sqrt{m/x})\), we have (recall that \(A \lesssim B\) means \(A = O(B)\)) \[\begin{align} \sqrt{f(x)} \lesssim \sqrt{\frac{s}{x}} + \min\left\{ \sqrt{\frac{m}{x}}, \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} \right\} + \frac{t^{1/(2k)} \sqrt{s}}{x}. \end{align}\] Thus, we can bound \(\|\boldsymbol{A}\boldsymbol{1}_S\|_{\Phi}\) as follows, using \(\sqrt{f(x)} \leq \sqrt{s\Delta}\) for \(x \leq 2C\): \[\begin{align} \|\boldsymbol{A}\boldsymbol{1}_S\|_{\Phi} &\lesssim \int_{x=0}^{2C} \sqrt{f(x)} \, dx + \int_{x=2C}^{\Delta} \sqrt{f(x)} \, dx \\ &\lesssim \int_{0}^{2C} \sqrt{s\Delta} \, dx + \int_{x=2C}^{\Delta} \sqrt{\frac{s}{x}} dx + \int_{x=2C}^{\Delta} \min\left\{ \sqrt{\frac{m}{x}}, \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} \right\} dx + \int_{x=2C}^{\Delta} \frac{t^{1/(2k)} \sqrt{s}}{x} \, dx \\ &\lesssim \sqrt{s\Delta} + t^{1/(2k)} \sqrt{s} \log \Delta + \int_{x=2C}^{\Delta} \min\left\{ \sqrt{\frac{m}{x}}, \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} \right\} dx. \end{align}\] Since \[\begin{align} \sqrt{\frac{m}{x}} \leq \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} &\iff x \leq \frac{s}{m^{(k-1)/(k+1)}}, \end{align}\] setting \(x^* = s/m^{(k-1)/(k+1)}\), we break the last integral into two parts: \[\begin{align} \int_{x=2C}^{\Delta} \min\left\{ \sqrt{\frac{m}{x}}, \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} \right\} dx \leq \int_{x=2C}^{x^*} \sqrt{\frac{m}{x}} dx + \int_{x=x^*}^{\Delta} \frac{s^{(k+1)/(2(k-1))}}{x^{k/(k-1)}} dx \lesssim m^{1/(k+1)} s^{1/2}. \end{align}\] Overall, we have \(\|\boldsymbol{A}\boldsymbol{1}_S\|_{\Phi} \lesssim (\sqrt{\Delta} + t^{1/(2k)} \log \Delta + m^{1/(k+1)}) \sqrt s\) as desired. ◻
Proposition 8. If Conjecture 1 holds, then we can list \(t\) \(2k\)-cycles in time \(\tilde{O}(m^{2k/(k+1)} + t)\).
Proof. From the AYZ approach described in Section 2.1 and Section 2.2, call a vertex “heavy” if its degree is more than \(\Delta\). The number of heavy vertices is at most \(2m/\Delta\); hence, the heavy cycles can be listed in time \(\tilde{O}(m^2/\Delta + t)\). The cycles involving light vertices can be listed in time \(\tilde{O}(\kappa_k(G) + t)\). From Lemma 4 and the bound on \(\|\boldsymbol{A}\|_\Phi\) from Lemma 7, we have \[\begin{align} \kappa_k(G) &\lesssim m \cdot \max_{p} \|\boldsymbol{A}_p\|_{\Phi}^{k-1}\\ &\lesssim m \cdot \left( \sqrt{\Delta} + t^{1/(2k)} \log \Delta + m^{1/(k+1)} \right)^{k-1} \\ &\lesssim m \cdot \Delta^{\frac{k-1}{2}} + m^{\frac{k-1}{k+1}} + t^{\frac{k-1}{2k}} \log^{k-1}\Delta\\ &= m\Delta^{\frac{k-1}{2}} + m^{\frac{2k}{k+1}} + mt^{\frac{k-1}{2k}} \log^{k-1}\Delta\\ (\text{Young's inequality}) &\lesssim m\Delta^{\frac{k-1}{2}} + m^{\frac{2k}{k+1}} + m^{\frac{2k}{k+1}} (\log\Delta)^{\frac{2k(k-1)}{k+1}} + t. \end{align}\] We balance the terms by setting \(\Delta = m^{2/(k+1)}\), yielding the desired runtime. ◻
3.3 The \(4\)-cycle queries↩︎
As an application of Lemma 7, we show how to obtain the \(\tilde{O}(m^{4/3} + t)\)-time algorithm for \(C_4\)-listing by reproving the following unbalanced supersaturation result for \(4\)-cycles, a special case of Conjecture 1 that is already known in the literature. We include the proof here as a warm-up.
Proposition 9 (Unbalanced supersaturation for \(4\)-cycles: the \(k=2\) case). Given a bipartite graph \(G=(A\cup B,E)\) with \(a:=|A|\), \(b:=|B|\) and \(m=\Omega(a+b+(ab)^{3/4})\) edges, there are \(\Omega(m^4/(a^2b^2))\) copies of \(C_4\).
Proof. Let \(t\) be the number of \(C_4\)’s and assume that \(a\ge b\) without loss of generality. For \(u\in A\), let \(d(u)\) be its degree. The number of \(2\)-paths whose middle vertex lies in \(A\) is \[P:=\sum_{u\in A}\binom{d(u)}{2} \ge a\binom{\frac{1}{a}\sum_{u\in A}d(u)}{2} =a\binom{m/a}{2} \ge \frac{m^2}{4a},\] where we used the convexity of \(x\mapsto x(x-1)/2\) and \(m\ge 2a\).
For \(x,y\in B, x \neq y\), let \(q(x,y):=|N(x)\cap N(y)|\). Then \(P=\sum_{\{x,y\}\subseteq B, x \neq y}q(x,y)\), and \[t=\sum_{\{x,y\}\subseteq B, x \neq y}\binom{q(x,y)}{2} \ge \binom b2\binom{P/\binom b2}{2} \ge \frac{P^2}{4\binom b2} \ge \frac{P^2}{2b^2} \ge \frac{m^4}{32a^2b^2}.\] Here we used \(P/\binom b2\ge 2\), which follows from the assumption on \(m\): for a sufficiently large constant, \(m\ge 2(ab)^{3/4}\ge 2a^{1/2}b\), since \(a\ge b\), and hence \(P\ge m^2/(4a)\ge b^2\ge 2\binom b2\). ◻
Corollary 10. We can list \(t\) \(4\)-cycles in time \(\tilde{O}(m^{4/3} + t)\).
4 Main Results↩︎
The key observation is that the structure of the proof of Theorem 1.1 of [26] can be adapted to the \(C_{2k}\)-listing setting. The first step is to replace the edge-bounding Lemma 3.4 of [26], which assumes \(C_{2k}\)-freeness, with a supersaturation version that depends on the number \(t\) of \(C_{2k}\)’s. We will use the following supersaturation result of Jiang and Yepremyan [35].
Lemma 11 (Jiang and Yepremyan [35]). Given a positive integer constant \(k\), there are positive constants \(c\) and \(d\), both depend on \(k\), such that the following holds. Let \(G\) be a graph with \(n\) vertices and \(m \geq c n^{1+1/k}\) edges. Then, \(G\) contains at least \(d(m/n)^{2k}\) copies of \(C_{2k}\).
Jiang and Yepremyan’s result can be used to obtain the following proposition. In what follows, the \(\lesssim, \gtrsim\) symbols, abbreviating \(\Omega\) and \(O\), hide (somewhat cumbersome) functions in \(k\). It is not hard to keep track on the dependence on \(c,d\) and the exponential in \(k\) factors arising throughout; we hide them for clarity of exposition.
Proposition 12. Let \(G=(A\cup B, E)\) be a bipartite graph with \(t\) \(C_{2k}\)’s, \(a=|A|\geq b=|B|\). Then, \(m=|E| \gtrsim ab^{1/k}\) implies \(t \gtrsim\frac{m^{2k}}{ a^k b^k}\).
Proof. First of all, from Lemma 11, the following always holds for any graph with \(N\) nodes, \(M\) edges, and \(T\) \(C_{2k}\) cycles: \[\begin{align} T \geq d (M/N)^{2k} - dc^{2k} N^{2}, \end{align}\] where \(c,d\) are the \(k\)-dependent parameters from Lemma 11. This is true because if \(M \geq cN^{1+1/k}\), then we have at least \(d(M/N)^{2k}\) cycles, and if \(M <cN^{1+1/k}\) the right hand side becomes negative.
Consider for a moment that \(a\) is a multiple of \(b\). We will drop this assumption later. We first handle the divisible case by showing that, if \(m\geq 4cab^{1/k}\), then \(t \gtrsim \frac{m^{2k}}{a^kb^k}\).
We begin by partitioning \(A\) randomly into \(r = a/b\) parts \(A_1, A_2, \ldots, A_r\) of size \(b\). Let \(G_i\) be the bipartite graph induced by \((A_i, B)\); let \(m_i\) be the number of edges in \(G_i\), and \(X_i\) the number of \(C_{2k}\)’s in \(G_i\). Then, we have \[\begin{align} X_i \geq d\left(\frac{m_i}{2b}\right)^{2k} - dc^{2k} (2b)^2. \end{align}\] Let \(X = \sum_{i=1}^r X_i\) be the total number of \(C_{2k}\)’s in the partition, then \[\begin{align} \mathop{\mathbb{E}}[X] \geq \sum_{i=1}^r \left[d\left(\frac{m_i}{2b}\right)^{2k} - dc^{2k} (2b)^2\right] \geq r \cdot d\left(\frac{\sum_i m_i}{2rb}\right)^{2k} - rdc^{2k} (2b)^2 = d\frac{m^{2k}}{(2b)^{2k} r^{2k-1}} - 4 dc^{2k} ab. \end{align}\] Given a cycle in \(G\), the probability that it is counted in \(X\) is \(r\binom b k / \binom a k \leq 1/r^{k-1}\) (there is a factor of \(r\) because there are \(r\) choices for which part the cycle lands on). Thus, \[\begin{align} \frac{t}{r^{k-1}} \geq \mathop{\mathbb{E}}[X] \geq d\frac{m^{2k}}{(2b)^{2k} r^{2k-1}} - 4dc^{2k} ab \end{align}\] which implies \[\begin{align} t \geq d\frac{m^{2k}}{(2b)^{2k} r^{k}} - 4dc^{2k} abr^{k-1} = d\frac{m^{2k}}{4^k a^{k}b^{k}} - 4dc^{2k} \frac{a^{k}}{b^{k-2}} \geq \frac{d}{2} \cdot \frac{m^{2k}}{4^k a^k b^k} \end{align}\]
Lastly, to treat the case where \(a\) is not a multiple of \(b\), we can add \(b\cdot \lceil a / b \rceil - a\) dummy vertices to \(A\), which in the worst case could double the size of \(A\), and apply the bound in the new graph. ◻
Our new edge bounding lemma is the following:
Lemma 13. Let \(G\) be an undirected graph with \(t\) \({2k}\)-cycles and let \(A,B\subseteq V(G)\). Then, the number of edges between \(A\) and \(B\) is at most \[\begin{align} |E(A,B)| \lesssim \left(|A| \cdot |B|^{1/k} + |B| \cdot |A|^{1/k}\right) + t^{1/(2k)} \cdot \sqrt{|A| \cdot |B|} \end{align}\]
Proof. Let \(M:=|E(A,B)|\). First suppose that \(A\cap B=\emptyset\). Let \(H\) be the bipartite graph with parts \(A,B\) and edge set \(E(A,B)\). Every \(C_{2k}\) in \(H\) is also a \(C_{2k}\) in \(G\), so \(H\) contains at most \(t\) such cycles. If \(M\lesssim \left( |A||B|^{1/k}+|B||A|^{1/k} \right)\), we are done. Otherwise, \(M\) is above the threshold of Proposition 12; hence \(t\geq \Omega(M^{2k}/(|A|^k|B|^k))\), and so \(M\lesssim t^{1/(2k)}\sqrt{|A||B|}\). Thus the desired bound holds in the case when \(A\) and \(B\) are disjoint.
For the general case, let \(I:=A\cap B\). We split the vertices of \(I\) randomly between the two sides, obtaining disjoint sets \(A'\subseteq A\) and \(B'\subseteq B\). Each edge of \(E(A,B)\) appears in \(E(A',B')\) with probability at least \(1/2\). Therefore, for some choice of the split, \(|E(A',B')|\geq |E(A,B)|/2\). Thus, \[M \lesssim \left(|A||B|^{1/k} + |B||A|^{1/k} \right) + t^{1/(2k)}\sqrt{|A||B|}.\] ◻
Using this edge bound on the \(\Phi\)-norm of an adjacency matrix of a graph with bounded degree, we bound the number of capped \(k\)-walks:
Lemma 14. Let \(G\) be a graph with maximum degree \(\Delta\) and \(t\) \(C_{2k}\)’s, and \(\boldsymbol{A}\) be its adjacency matrix. Then, \[\|\boldsymbol{A}\|_{\Phi} \lesssim m^{\frac{1}{2k}} \Delta^{\frac{1}{2} - \frac{1}{2k}} + t^{\frac{1}{2k}} \log \Delta.\]
Proof. By Lemma 5, it is sufficient to show that, for any subset \(S\) of vertices of \(G\), we have \[\begin{align} \|\boldsymbol{A} \boldsymbol{1}_S\|_{\Phi} \lesssim m^{\frac{1}{2k}} \Delta^{\frac{1}{2} - \frac{1}{2k}} + t^{\frac{1}{2k}} \log \Delta \cdot \sqrt{|S|}. \end{align}\] Let \(E(v,S)\) denote the set of edges between \(v\) and \(S\). Define \[\begin{align} f(x) := |\{ v : |E(v,S)| \geq x \}| \end{align}\] Then, our goal is to bound \(\|\boldsymbol{A}\boldsymbol{1}_S\|_{\Phi} = \sum_{x=1}^{\Delta} \sqrt{f(x)}\), subject to the constraints we know about \(f\). We will write down the constraints later, but first we break this sum in to dyadic intervals. For \(i \in \{0, 1, \ldots, \lceil \log \Delta \rceil\}\), define \[\begin{align} B_i & := \{ v : 2^i \leq |E(v,S)| < 2^{i+1} \} \\ b_i & := |B_i|. \end{align}\] Then, because \(f(x)\) is non-increasing in \(x\), we have \[\begin{align} \|\boldsymbol{A} \boldsymbol{1}_S\|_{\Phi} &= \sum_{i=0}^{\lceil \log \Delta \rceil} \sum_{x=2^i}^{2^{i+1}-1} \sqrt{f(x)} \\ &\leq \sum_{i=0}^{\lceil \log \Delta \rceil} (2^{i+1}-2^i) \sqrt{f(2^i)} \leq \sum_{i=0}^{\lceil \log \Delta \rceil} 2^i \sqrt{f(2^i)} \\ &\leq \sum_{i=0}^{\lceil \log \Delta \rceil} 2^i \sqrt{\sum_{j=i}^{\lceil \log \Delta \rceil} b_j} \leq \sum_{i=0}^{\lceil \log \Delta \rceil} 2^i \sum_{j=i}^{\lceil \log \Delta \rceil} \sqrt{b_j} \\ &= \sum_{j=0}^{\lceil \log \Delta \rceil} \sqrt{b_j} \sum_{i=0}^{j} 2^i \leq 2 \sum_{j=0}^{\lceil \log \Delta \rceil} 2^j \sqrt{b_j} \end{align}\] So our next job is to bound the quantity \(2^j \sqrt{b_j}\) for each \(j\). To do this, fix a \(j \in \{ 0, 1, \ldots, \lceil \log \Delta \rceil\}\). To shorten notations, let \(B = B_j\), \(b = b_j\), \(s = |S|\), and \(d = 2^j\). Then, we have the following constraints: \[\begin{align} |E(B, S)| &\lesssim \left( sb^{1/k} + bs^{1/k} \right) + t^{1/(2k)} \cdot \sqrt{sb} \\ |E(B, S)| &\lesssim s\Delta \\ bd \lesssim |E(B, S)| &\leq m. \end{align}\]
Define \(x = bd^2/s\), then we have the following bounds on \(x\): \[\begin{align} x &= \frac{bd^2}{s} = d \frac{bd}{s} \leq d \frac{s\Delta}{s} = d \Delta \\ x &= \frac{bd^2}{s} = \frac{(bd)^2}{bs}\\ &\lesssim \frac{\left (sb^{1/k} + bs^{1/k} + t^{1/(2k)} \cdot \sqrt{sb}\right )^2}{bs} \\ &\lesssim \frac{(sb^{1/k})^2 + (bs^{1/k})^2 + (t^{1/(2k)} \cdot \sqrt{sb})^2}{bs} \\ &= \left( s b^{2/k - 1} + bs^{2/k - 1} \right) + t^{1/k}\\ &= \left(\frac{bd^2}{x} b^{2/k - 1} + \left(\frac{b}{s}\right)^{1-2/k}b^{2/k}\right) + t^{1/k}\\ &\lesssim \left(\frac{d^2b^{2/k}}{x} + \left(\frac{\Delta}{d}\right)^{1-2/k} \left(\frac{m}{d}\right)^{2/k}\right) + t^{1/k}\\ &= \left( \frac{d^2b^{2/k}}{x} + \frac{\Delta^{1-2/k} m^{2/k}}{d}\right) + t^{1/k}. \end{align}\]
Now we use the fact that \(x \leq \frac{P}{x} + Q\) implies \(x = O(P^{1/2} + Q)\) to obtain that \[\begin{align} x &\lesssim \sqrt{d^2b^{2/k}} + \frac{\Delta^{1-2/k} m^{2/k}}{d} + t^{1/k} \\ &= d b^{1/k} + \frac{\Delta^{1-2/k} m^{2/k}}{d} + t^{1/k}\\ &\lesssim (db)^{1/k}d^{1-1/k} + \frac{\Delta^{1-2/k} m^{2/k}}{d} + t^{1/k}\\ &\lesssim m^{1/k} d^{1-1/k} + \frac{\Delta^{1-2/k} m^{2/k}}{d} + t^{1/k} \end{align}\]
Along with the fact that \(x \lesssim d\Delta\), we have \[\begin{align} x &\lesssim \min \left\{m^{1/k} d^{1-1/k} + \frac{\Delta^{1-2/k} m^{2/k}}{d} + t^{1/k}, d \Delta \right\} \\ &\lesssim m^{1/k} d^{1-1/k} + \min \left\{\frac{\Delta^{1-2/k} m^{2/k}}{d}, d \Delta \right\} + t^{1/k}. \end{align}\]
This implies \[\begin{align} \frac{2^j \sqrt{b_j}}{\sqrt s} = \frac{d \sqrt{b}}{\sqrt{s}} =\sqrt x \lesssim m^{\frac{1}{2k}} 2^{j\frac{k-1}{2k}} + \min \left\{\frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{2^{j/2}}, 2^{j/2} \sqrt \Delta \right\} + t^{\frac{1}{2k}}. \end{align}\] We bound the sum over \(j\) of each of the first two terms separately. For the first term we have \[\begin{align} m^{1/2k} \sum_{j=0}^{\lceil \log \Delta \rceil} 2^{j(\frac{k-1}{2k})} & \frac{2^{(\lceil \log \Delta \rceil + 1)(\frac{k-1}{2k})} - 1}{2^{\frac{k-1}{2k}} - 1} \\ &\lesssim m^{1/2k} 2^{\lceil \log \Delta \rceil (\frac{k-1}{2k})} \\ &\lesssim m^{1/2k} \Delta^{\frac{k-1}{2k}}. \end{align}\] For the second term, we need to find the value of \(j \in \{0, 1, \ldots, \lceil \log \Delta \rceil\}\) that transitions between the two cases in the minimum. In particular, \[\frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{2^{j/2}} \leq 2^{j/2} \sqrt \Delta \qquad \text{ if and only if } \qquad j \geq j^* := \lceil \log_2 ( m/\Delta)^{1/k} \rceil.\] Hence, let’s break the sum into two parts: \[\begin{align} \sum_{j=0}^{\lceil \log \Delta \rceil} \min \left\{ \frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{2^{j/2}}, 2^{j/2} \sqrt \Delta \right\} &= \sum_{j=0}^{j^*} 2^{j/2} \sqrt \Delta + \sum_{j=j^*+1}^{\lceil \log \Delta \rceil} \frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{2^{j/2}} \\ &\lesssim 2^{j^*/2} \sqrt \Delta + \frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{2^{j^*/2}} \\ &\lesssim (m/\Delta)^{1/(2k)} \sqrt \Delta + \frac{\Delta^{\frac{k-2}{2k}} m^{1/k}}{(m/\Delta)^{1/(2k)}} \\ &\lesssim m^{1/(2k)} \Delta^{\frac{k-1}{2k}}. \end{align}\]
And thus, \(\sum_j 2^j \sqrt{b_j}\) has an extra \(\log \Delta\) factor only on the \(t^{1/(2k)}\) term, yielding the desired bound. ◻
Next, we prove the analog of Lemma 1.7 of [26] for the listing problem. Recall the quantity \(\kappa_k(G)\) defined in Section 2.2, which is the maximum number of capped \(k\)-walks starting from a vertex in \(G\).
Lemma 15. Let \(G\) be an undirected graph with maximum degree \(\Delta\) and \(t\) \(C_{2k}\)’s. Then, \[\begin{align} \kappa_k(G) \lesssim m^{\frac{3}{2} - \frac{1}{2k}} \Delta^{\frac{(k-1)^2}{2k}} + m^{\frac{2k}{k+1}} (\log\Delta)^{\frac{2k(k-1)}{k+1}} + t \end{align}\]
Proof. Let \(\boldsymbol{A}_p\) be the adjacency matrix of the graph induced by the \(\bar{V}_p\). Using Lemma 14 we have \[\begin{align} \kappa_k(G) &\lesssim m \cdot \max_{p} \|\boldsymbol{A}_p\|_{\Phi}^{k-1}\\ &\lesssim m \left( m^{\frac{1}{2k}} \Delta^{\frac{1}{2} - \frac{1}{2k}} + t^{\frac{1}{2k}} \log \Delta \right)^{k-1} \\ &\lesssim m \cdot (m^{\frac{k-1}{2k}} \Delta^{\frac{(k-1)^2}{2k}} + t^{\frac{k-1}{2k}} \log^{k-1}\Delta)\\ &= m^{\frac{3k-1}{2k}} \Delta^{\frac{(k-1)^2}{2k}} + mt^{\frac{k-1}{2k}} \log^{k-1}\Delta\\ (\text{Young's inequality}) &\lesssim \left( m^{\frac{3}{2} - \frac{1}{2k}} \Delta^{\frac{(k-1)^2}{2k}} + m^{\frac{2k}{k+1}} (\log\Delta)^{2k(k-1)/(k+1)} + t \right) \end{align}\] ◻
Finally, we prove the main result of this paper, that we can list \(2k\)-cycles in undirected graphs more efficiently than what the AYZ-time can achieve:
Theorem 16. Let \(G\) be an undirected graph with \(m\) edges and \(n\) vertices. We can list all \(2k\)-cycles in \(G\) in time \(\lesssim m^{\frac{2k^2-k+1}{k^2+1}}\log n + t \log n\), where \(t\) is the number of \(2k\)-cycles.
Proof. From the AYZ approach described in Section 2.1 and Section 2.2, call a vertex “heavy” if its degree is more than \(\Delta\). The number of heavy vertices is at most \(2m/\Delta\); hence, the heavy cycles can be listed in time \(\tilde{O}(m^2/\Delta + t)\). The cycles involving light vertices can be listed in time \(\tilde{O}(\kappa_k(G) + t)\), which is \[\widetilde{O}( m^{\frac{3}{2} - \frac{1}{2k}} \Delta^{\frac{(k-1)^2}{2k}} + m^{\frac{2k}{k+1}} (\log\Delta)^{\frac{2k(k-1)}{k+1}} + t ).\] We balance the two terms by setting \(\Delta = m^{\frac{k+1}{k^2+1}}\), yielding a runtime of \(\widetilde{O}(m^{\frac{2k^2-k+1}{k^2+1}} + t)\). The poly-log factor is absorbed because \(m^{\frac{2k^2-k+1}{k^2+1}}\) dominates \(m^{\frac{2k}{k+1}} (\log\Delta)^{\frac{2k(k-1)}{k+1}}\). ◻
5 Conclusions↩︎
We presented the first improvement to the AYZ even cycle listing result in 30 years. Building on the capped-\(k\)-walk framework of Dahlgaard, Knudsen, and Stöckel [26] and the supersaturation result of Jiang and Yepremyan [35], we proved that all \(2k\)-cycles in an undirected \(m\)-edge graph can be listed in time \(O\!\left(m^{(2k^2-k+1)/(k^2+1)} + t\right)\), where \(t\) is the output size. For \(k = 3\), our algorithm matches the exponent of Vassilevska Williams and Westover [30] while avoiding large polylogarithmic factors, computer-assisted case analysis, and BFS-based subroutines. Our algorithms are expressed as query plans over multiple tree decompositions, using only join and project operators, making them amenable to efficient implementation in database systems.
Several open problems remain.
5.0.0.1 Tightness of the exponent.
The exponent \((2k^2-k+1)/(k^2+1)\) is unlikely to be optimal for all \(k\). For \(k = 2\), the tight bound for \(4\)-cycle listing is \(\Theta(m^{4/3})\) [28], [29], whereas our formula gives \(m^{7/5}\).
5.0.0.2 More general conjunctive queries.
Our techniques apply specifically to even cycle queries, which involve a single symmetric binary relation (the edge relation of an undirected graph). A natural and important open problem is to generalize these ideas to broader classes of conjunctive queries where some of the relations are symmetric and there are a lot of self-joins. The symmetry of the edge relation was exploited crucially in our analysis — through the Bondy–Simonovits theorem and the capped-\(k\)-walk argument — and it is unclear how to extend these ideas to asymmetric or higher-arity settings.
5.0.0.3 Supersaturation beyond graphs.
The key technical ingredient in our work is a supersaturation result for bipartite graphs, derived from the Jiang–Yepremyan theorem. A deeper open question is whether analogous supersaturation results hold for hypergraph patterns or, more generally, for relations beyond binary ones. Such results would be a prerequisite for extending our approach to a richer class of conjunctive queries, and may be of independent interest in extremal combinatorics.