Faster shortest-path algorithms using the acyclic-connected tree

Abstract

We provide a method to obtain beyond-worst-case time complexity for any single-source-shortest-path (SSSP) algorithm by exploiting modular structures in graphs. The key novelty is a graph decomposition, called the acyclic-connected (A-C) tree, which breaks up a graph into a recursively nested sequence of strongly connected components in topological order. The A-C tree is optimal in the sense that it maximally decomposes the graph, formalised by a parameter called nesting width, measuring the extent to which a graph can be decomposed. We show how to compute the A-C tree in linear time, allowing it to be used as a preprocessing step for SSSP. Indeed, we transform any SSSP algorithm by first computing the A-C tree, and then running the SSSP algorithm in a careful recursive manner on the A-C tree. We illustrate this with two state-of-the-art algorithms: Dijkstra's algorithm and the recent sparse graph algorithm of Duan et al., obtaining improved time complexities of $O(m+n\log(\mathrm{nw}(G)))$ and $O(mα(n)+m\log^{2/3}(\mathrm{nw}(G)))$, respectively, where $\mathrm{nw}(G) \leq n$ is the nesting width of the graph $G$, and $α(n)$ is the extremely slow-growing inverse Ackermann function. Some classes of graphs, such as directed acyclic graphs, have bounded nesting width, and we obtain linear-time SSSP algorithms for these graphs.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.