Polylog-time and near-linear work approximation scheme for undirected shortest paths

Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses along-standing open problem. Our main result is an O(mn’O + s(m + nl+’O )) work polylog-time randomized algorithm that computes paths within (1+0(1/ polylog n)) of shortest from s source nodes to alI other nodes in weighted undirected networks with n nodes and m edges (for any fixed co > O). This work bound nearly matches the O(sm) sequential time. In contrast, previous polylog-time algorithms required min { 6( n3 ), ~ (m2 ) } work (even when s = 1), and previous near-linear work algorithms required near-O(n) time. Another result is faster shortest-paths algorithms if accurate distances are required only between “distant” vertices: We obtain an O((m + sn)n’” ) time algorithm that computes paths of weight (1 + 0(1/ pdybg n))dist + o(w~.. polylog n), where dist is the corresponding distance and wmaX is the maximum edge weight. Our chief instrument, which is of independent int crest, are efficient constructions of sparse hop sets. A (d, c)-hop set of a network G = (V, E) is a set E* of new weighted edges such that minimum-weight d-edge pat hs in (V, E u E*) have weight within (1 + c) of the respective dist antes in G. We construct hop sets of size O(nl+’O ) where e = 0(1/ polylog n) and d = O(polylog n).