2026/07/16 by Frank Bauernöppel, Jörg-Rüdiger Sack
#cs.DS
Enumerating simple paths and cycles subject to a given length bound is a fundamental problem in graph algorithms with applications ranging from network analysis to computational biology. Recent algorithms for this problem, namely CYCLESEARCH (Gupta and Suzumura, arXiv:2105.10094v2) and BC-DFS (Peng et al. 2019, 2021), employ barrier values to prune fruitless searches. Both algorithms have been shown incomplete and their delay-bound arguments rely on monotonicity claims that are flawed. For CYCLESEARCH this was shown previously (arXiv:2512.08392). In this paper we establish the analogous results for BC-DFS by presenting new counter-examples and identifying a defect in its barrier-update procedure. As our main contribution, we introduce the concept of edge-consistency, a local invariant on barrier values analogous to heuristic consistency in informed search. Edge-consistency provides an incremental mechanism for maintaining admissible barrier estimates and yields concise correctness proofs. We use edge-consistency as a unifying framework for design and analysis of Bounded-Scope Depth-First Search (BS-DFS) -- a new O(k(n+m)) delay algorithm for enumerating simple paths or cycles of length at most k in a directed graph -- and of several variants of it. We also use edge-consistency to pinpoint the precise failure mechanism of BC-DFS. Experimental results confirm that the omissions in BC-DFS are not isolated edge cases and occur with noticeable frequency on random graphs.