Parallel Shortest Paths Using Radius Stepping

Abstract

The single-source shortest path problem (SSSP) with nonnegative edge weights is notoriously difficult to solve efficiently in parallel---it is one of the graph problems said to suffer from the transitive-closure bottleneck. Yet, 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). Building on the success of Δ-stepping, this paper describes Radius Stepping, an algorithm with one of the best-known tradeoffs between work and depth bounds for SSSP with nearly-linear (~O(m)) work. The algorithm is a Δ-stepping-like algorithm but uses a variable instead of a 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(n/ρ log ρ L), for a total of O(kn/ρ log ρ L) substeps, each parallel. We describe how to preprocess a graph to have this property. Altogether, for an arbitrary input graph with n vertices and m edges, Radius Stepping, after preprocessing, takes O((m+nρ)log n) work and $O(n/ρ log n log (ρ L)) depth per source. The preprocessing step takes O(m log n + nρ2) work and O(ρlog ρ) depth, adding no more than O(nρ) edges.