Optimal Listing of Cycles and st-Paths in Undirected Graphs

International audienceListing 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(n2). 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+Pc2C(G) |c|) time and is asymptotically optimal: indeed, (m) time is necessarily required to read G as input, and (Pc2C(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 ( + m) = ( ) time, thus saving O(m + n) = O(n2) 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 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 +P 2Pst(G) | |) time, observing that (P 2Pst(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 Pst(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 Bs,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 Bs,t. 3. Recursively list the st-paths in Bs,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 Bs,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 Bs,t, which guarantees that there exists at least one new solution in the current Bs,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 Bs,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