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

ABSTRACT

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 a long-standing open problem. Our main result is an Omn^e0+s m+n^1+e0 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 &egr;0>0). This work bound nearly matches the O&d5;sm sequential time. In contrast, previous polylog-time algorithms required nearly minO&d5; n³,O&d5; m² 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 Om+snn^{e 0} time algorithm that computes paths of weight (1+O(1/polylog n) dist + O(wmax polylog n), where dist is the corresponding distance and wmax is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets. A (d,&egr;)-hop set of a network G=(V,E) is a set E* of new weighted edges such that mimimum-weight d-edge paths in V,E∪E^* have weight within (1+&egr;) of the respective distances in G. We construct hop sets of size On^1+e0 where &egr;=O(1/polylog n) and d=O(polylog n).

REFERENCES

• 1: AWERBUCH, B., BERGER, B., COWEN, L., AND PELEG, D. 1993. Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 638-647.
• 2: AWERBUCH, B., AND PELEG, D. 1990. Sparse partitions. In Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 503-513.
• 3: Edith Cohen, Efficient parallel shortest-paths in digraphs with a separator decomposition, Journal of Algorithms, v.21 n.2, p.331-357, Sept. 1996 [doi>10.1006/jagm.1996.0048]
• 4: Edith Cohen, Using selective path-doubling for parallel shortest-path computations, Journal of Algorithms, v.22 n.1, p.30-56, Jan. 1997 [doi>10.1006/jagm.1996.0813]
• 5: Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: KLEIN, P. N. 1992. A parallel randomized approximation scheme for shortest paths. Draft of journal version.
• 8: Philip N. Klein , S. Sairam, A parallel randomized approximation scheme for shortest paths, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.750-758, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129785]
• 9: KLEIN, P. N., AND SAIRAM, S. 1993. A linear-processor polylog-time algorithm for shortest paths in planar graphs. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 259-270.
• 10: Thomas H. Spencer, Time-work tradeoffs for parallel algorithms, Journal of the ACM (JACM), v.44 n.5, p.742-778, Sept. 1997 [doi>10.1145/265910.265923]
• 11: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory