Listing all the simple cycles (hereafter just called cycles) in a graph is a classical problem whose efficient solutions date back to the early 70s. For a graph with n vertices and m edges, containing η cycles, the best known solution in the literature is given by Johnson's algorithm [SIAM J. Computing, 1975] and takes O((η + 1)(m + n)) time. This solution is surprisingly not optimal for undirected graphs: to the best of our knowledge, no theoretically faster solutions have been proposed in almost 40 years. We present the first optimal solution to list all the cycles in an undirected graph G, improving the time bound of Johnson's algorithm by a factor that can be O(n 2 ). Specifically, let C(G) denote the set of all these cycles, and observe that |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) |c|) time and is asymptotically optimal: indeed, Ω(m) time is necessarily required to read G as input, and Ω( c∈C(G) |c|) time is necessarily required to list the output. We then describe an infinite family of dense graphs, in which each graph with n vertices and m edges contains η = Ω(m) cycles c with |c| = O(1) edges. For each graph in this family, our algorithm requires 2 ) time when compared to Johnson's algorithm. In general for any graph, since |c| ≤ n, the cost of our algorithm never exceeds O(m + (η + 1)n) time. 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 P st (G) denote the set of st-paths in G and, for an st-path π ∈ P st (G), let |π| be the number of edges in π. Our algorithm lists all the st-paths in G optimally in O(m + π∈Pst(G) |π|) time, observing that Ω( π∈Pst(G) |π|) time is necessarily required to list the output. While the basic approach is simple (see binary partition in point 3), we use a number of non-trivial ideas to obtain our optimal algorithm for an undirected (connected) graph G as conceptually listed below. 1. Prove the following reduction. If there exists an optimal algorithm to list the st-paths in G, there exists an optimal algorithm to list the cycles in G. This relates C(G) and P st (G) for some choices s, t. 2. Focus on listing the st-paths. Consider the decomposition of the graph into biconnected components (bccs), thus forming a tree T where two bccs are adjacent in T iff they share an articulation point. Exploit (and prove) the property that if s and t belong to distinct bccs, then (i) there is a unique sequence B s,t of adjacent bccs in T through which each st-path must necessarily pass, and (ii) each st-path is the concatenation of paths connecting the articulation points of these bccs in B s,t . 3. Recursively list the st-paths in B s,t using the classical binary partition (i.e. given an edge e in G, list all the cycles containing e, and then all the cycles not containing e): now it suffices to work on the first bcc in B s,t , and efficiently maintain it when deleting an edge e, as required by the binary partition. 4. Use a notion of certificate to avoid recursive calls (in the binary partition) that do not list new st-paths. This certificate is maintained dynamically as a data structure representing the first bcc in B s,t , which guarantees that there exists at least one new solution in the current B s,t . 5. Consider the binary recursion tree corresponding to the binary partition. Divide this tree into spines: a spine corresponds to the recursive calls generated by the edges e belonging to the same adjacency list in B s,t . The amortized cost for each listed st-path π is O(|π|) if there is a guarantee that the amortized cost in each spine S is O(µ), where µ is a lower bound on the number of st-paths that will be listed from the recursive calls belonging to S. The (unknown) parameter µ different for each spine S, and the corresponding cost O(µ), will drive the design of the proposed algorithms.
For undirected graphs, recently Ferreira et.al REF presented a more optimal algorithm.
Optimal Listing of Cycles and st-Paths in Undirected Graphs
ArXiv
ArXiv
Mathematics Computer Science