Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Abstract

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=Ω(n^{2})$, our reachability and shortest path algorithms have depth only $n^{0.136}$ and $n^{0.25+o(1)}$, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems require $Ω(\sqrt{n})$ depth in all density regimes.

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.