Optimal Listing of Cycles and st-Paths in Undirected Graphs

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 C(G) denote the set of all these cycles (|C(G)| = η). For a cycle c ∈ C(G), let |c| denote the number of edges in c. Our algorithm requires O(m + ∑c∈C(G) lcl) time and is asymptotically optimal: Ω(m) time is necessarily required to read G as input, and Ω(∑c∈C(G) |c|) 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 Pst(G) denote the set of st-paths in G and, for an st-path π ∈ Pst(G), let |π| be the number of edges in π. Our algorithm lists all the st-paths in G optimally in O(m + ∑π∈Pst(G) |π|) time.