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 art 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 a long-standing open problem. Our main result is an O(mn(epsilon 0) + s(m + n(1+epsilon 0))) work polylog-time randomized algorithm that computes paths within (1 + O(1/polylog n)) of shortest from s source nodes to all other nodes in weighted undirected networks with n nodes and m edges (for any fixed epsilon(0) > 0), This work bound nearly matches the O(sm) sequential time. In contrast, previous polylog-time algorithms required min{O(n(3)), O(m(2))} work (even when s = 1), and previous near-linear work algorithms required near-O(n) time. We also present faster sequential algorithms that provide good approximate distances only between "distant" vertices: We obtain an O((m + sn)n(epsilon 0)) time algorithm that computes paths of weight (1 + O(1/polylog n)) dist + O(w(max) polylog n), where dist is the corresponding distance and w(max) is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets. A (d, epsilon)-hop set of a network G = (V. E) is a set E* of new weighted edges such that minimum-weight d-edge paths in (V, E U E*) have weight within (1 + epsilon) of the respective distances in G. We construct hop sets of size O(n(1+epsilon 0)) where epsilon = O(1/polylog n) and d = O(polylog n).