Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

Understand

We present a $(1+\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving $\mathrm{poly}(\log n)$ depth and $m\mathrm{poly}(\log n)$ work for $n$-nodes $m$-edges graphs.

• Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge.
• For $(1+\varepsilon)$-approximation, all prior algorithms with $\mathrm{poly}(\log n)$ depth perform at least $\Omega(mn^{c})$ work for some constant $c>0$.
• Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for $25$ years.