Optimal Listing of Cycles and st-Paths in Undirected GraphsProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

The classical problem of efficiently listing all the simple cycles in a graph has been studied since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most efficient solution was presented by Johnson [SIAM J. Computing, 1975] and takes O((η + 1)(m + n)) time. This solution is not optimal for undirected graphs: nevertheless, no theoretical improvements have been proposed in the past decades.We present the first optimal solution to list all the simple cycles in an undirected graph G. Specifically, let (G) denote the set of all these cycles (|(G)| = η). For a cycle c ∊ (G), let |c| denote the number of edges in c. Our algorithm requires time and is asymptotically optimal: Ω(m) time is necessarily required to read G as input, and time is required to list the output.We also present the first optimal solution to list all the simple paths from s to t (shortly, st-paths) in an undirected graph G. Let st(G) denote the set of st-paths in G and, for an st-path π ∊ st(G), let |π| be the number of edges in π. Our algorithm lists all the st-paths in G optimally in time.Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973105.13