Parallel Shortest-Paths Using Radius Stepping

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 $Δ$-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 $Δ$. Each step settles the vertices in its annulus but can take $Θ(n)$ substeps, each requiring $Θ(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 $Δ$-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, ρ)$-graph property and show that if an undirected graph has this property, then the number of steps can be bounded by $O(\frac{n}ρ \log ρL)$, for a total of $O(\frac{kn}ρ \log ρ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}ρ)$ work and $O(\frac{n}ρ\log n \log (ρL))$ depth per source after preprocessing. The preprocessing step can be done in $O(m\log n + nρ^2)$ work and $O(ρ^2)$ depth or in $O(m\log n + nρ^2\log n)$ work and $O(ρ\log ρ)$ depth, and adds no more than $O(nρ)$ edges.