Enumerating Length-Bounded Simple Paths and Cycles in Directed Graphs with $O(k(n+m))$ Delay Using Edge-Consistent Node Barriers
For researchers in graph algorithms, this work provides a correct and efficient algorithm for a fundamental enumeration problem, while exposing and fixing flaws in prior methods.
The authors identify flaws in existing barrier-based algorithms for enumerating length-bounded simple paths and cycles, and introduce edge-consistency to design BS-DFS, a new algorithm with O(k(n+m)) delay. Experiments show that omissions in prior algorithms occur frequently on random graphs.
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 CYCLE_SEARCH (Gupta and Suzumura, 2021) 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 CYCLE_SEARCH this was shown previously. 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.