2025/12/09 by Frank Bauernöppel, Jörg-Rüdiger Sack, Bauernöppel, Frank +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2512.08392
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 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.