Finding All Bounded-Length Simple Cycles in a Directed Graph -- Revisited
For researchers working on graph cycle enumeration, this work corrects an error in a recent algorithm and provides a correct alternative with proven delay bounds.
The authors identify and fix a flaw in a previously proposed algorithm for enumerating bounded-length simple cycles in directed graphs, showing that the original algorithm fails to enumerate certain valid cycles and has a gap in its delay bound proof. Their new algorithm, SimpleSearch, achieves a delay bound of O(k(n+m)) per cycle output or termination.
In 2021, Gupta and Suzumura proposed a novel algorithm for enumerating all bounded-length simple cycles in directed graphs (arXiv:2105.10094). In this work, we present a concrete counter-example demonstrating that the proposed algorithm fails to enumerate certain valid cycles. Analyzing it, we pinpoint the precise step at which the original correctness proof breaks down. We also identify a gap in the original proof of the delay bound claimed. Finally, we propose algorithm \textsc{SimpleSearch} avoiding these flaws by construction, while achieving the delay bound $O(k(n + m))$ per cycle output or termination; where $k$ is the length bound, $n$ the number of nodes, and $m$ the number of edges in the finite simple directed graph $G$.