Enumerating Small Cycles
2026-07-29 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors build on earlier work that found fast ways to detect even-length cycles in graphs. They extend these results to not only detect but efficiently list many cycles of lengths 8 to 16, improving the known algorithms. Their method preprocesses the graph quickly and then outputs each cycle with very little delay. They also provide algorithms to list all cycles within certain size ranges efficiently for any fixed cycle length. This work improves how easily specific cycle patterns can be found and enumerated in large graphs.
graph theorycycle detectionenumeration algorithmeven cyclestime complexitypreprocessingalgorithmic delaygraph enumeration
Authors
Or Stern, Or Zamir
Abstract
In a seminal result of Yuster and Zwick, they showed that for any fixed $k$, the even cycle $C_{2k}$ can be detected in an $n$-vertex graph in time $O(n^2)$. For $4$-cycles, a folklore algorithm extends to listing: for any $t$, we can list $t$ different $4$-cycles, if such exist, in $O(n^2+t)$ time. Recently, Jin, Vassilevska-Williams, and Zhou obtained similar bounds for listing $6$-cycles. In this work, we generalize the above to cycles of sizes $8, 10, 12, 14,$ and $16$; we show that for all $k\leq 8$, we can list $t$ distinct $2k$-cycles in $\tilde{O}(n^2+t)$ time. In fact, our algorithm gives enumeration with pre-processing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$. Additionally, for any fixed $k$, we present an optimal enumeration (and hence also listing) algorithm for all cycles of size at most $2k$. More generally, for any fixed $k$ and any $3\le i\le \frac{4k}{3}$, we present an algorithm with preprocessing time $\tilde{O}(n^2)$ and delay $\tilde{O}(1)$ that enumerates all cycles of sizes in the range $[i,2k]$.