Abstract
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 of $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$.
Conclusion
Our study not only uncovers the limitations of the original algorithm but also presents a more effective solution, advancing research in directed graphs.
Blogger's Review: This article's reflection and improvement on the original algorithm are of significant importance, especially in the field of graph theory. The proposed \textsc{SimpleSearch} algorithm showcases innovation in complexity control, warranting further research and application. Future work should continue to deepen this direction.