Parallel Shortest-Paths Using Radius Stepping

Abstract

The single-source shortest path problem (SSSP) with nonnegative edge weights is a notoriously difficult problem to solve efficiently in parallel---it is one of the graph problems said to suffer from the transitive-closure bottleneck. In practice, the $\hat{I}”$-stepping algorithm of Meyer and Sanders (J. Algorithms, 2003) often works efficiently but has no known theoretical bounds on general graphs. The algorithm takes a sequence of steps, each increasing the radius by a user-specified value $\hat{I}”$. Each step settles the vertices in its annulus but can take $\hat{I}˜(n)$ substeps, each requiring $\hat{I}˜(m)$ work ($n$ vertices and $m$ edges). In this paper, we describe Radius-Stepping, an algorithm with the best-known tradeoff between work and depth bounds for SSSP with nearly-linear ($\otilde(m)$) work. The algorithm is a $\hat{I}”$-stepping-like algorithm but uses a variable instead of fixed-size increase in radii, allowing us to prove a bound on the number of steps. In particular, by using what we define as a vertex $k$-radius, each step takes at most $k+2$ substeps. Furthermore, we define a $(k,\ddot{I})$-graph property and show that if an undirected graph has this property, then the number of steps can be bounded by $O(\frac{n}{\ddot{I}}\log \ddot{I}L)$, for a total of $O(\frac{kn}{\ddot{I}}\log \ddot{I}L)$ substeps, each parallel. We describe how to preprocess a graph to have this property. Altogether, Radius-Stepping takes $O((m+n\log n)\log \frac{n}{\ddot{I}})$ work and $O(\frac{n}{\ddot{I}}\log n\log (\ddot{I}L))$ depth per source after preprocessing. The preprocessing step can be done in $O(m\log n+n\ddot{I}{}^2)$ work and $O(\ddot{I}{}^2)$ depth or in $O(m\log n+n\ddot{I}{}^2\log n)$ work and $O(\ddot{I}\log \ddot{I})$ depth, and adds no more than $O(n\ddot{I})$ edges.