Faster Distributed Shortest Path Approximations via Shortcuts

Authors Bernhard Haeupler, Jason Li



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.33.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Bernhard Haeupler
  • Carnegie Mellon University, USA, http://cs.cmu.edu/~haeupler
Jason Li
  • Carnegie Mellon University, USA, http://cs.cmu.edu/~jmli

Cite AsGet BibTex

Bernhard Haeupler and Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.33

Abstract

A long series of recent results and breakthroughs have led to faster and better distributed approximation algorithms for single source shortest paths (SSSP) and related problems in the CONGEST model. The runtime of all these algorithms, however, is Omega~(sqrt{n}), regardless of the network topology, even on nice networks with a (poly)logarithmic network diameter D. While this is known to be necessary for some pathological networks, most topologies of interest are arguably not of this type. We give the first distributed approximation algorithms for shortest paths problems that adjust to the topology they are run on, thus achieving significantly faster running times on many topologies of interest. The running time of our algorithms depends on and is close to Q, where Q is the quality of the best shortcut that exists for the given topology. While Q = Theta~(sqrt{n} + D) for pathological worst-case topologies, many topologies of interest have Q = Theta~(D), which results in near instance optimal running times for our algorithm, given the trivial Omega(D) lower bound. The problems we consider are as follows: - an approximate shortest path tree and SSSP distances, - a polylogarithmic size distance label for every node such that from the labels of any two nodes alone one can determine their distance (approximately), and - an (approximately) optimal flow for the transshipment problem. Our algorithms have a tunable tradeoff between running time and approximation ratio. Our fastest algorithms have an arbitrarily good polynomial approximation guarantee and an essentially optimal O~(Q) running time. On the other end of the spectrum, we achieve polylogarithmic approximations in O~(Q * n^epsilon) rounds for any epsilon > 0. It seems likely that eventually, our non-trivial approximation algorithms for the SSSP tree and transshipment problem can be bootstrapped to give fast Q * 2^O(sqrt{log n log log n}) round (1+epsilon)-approximation algorithms using a recent result by Becker et al.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Distributed algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Distributed Graph Algorithms
  • Shortest Path
  • Shortcuts

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 79-88. ACM, 2014. Google Scholar
  2. Noga Alon, Richard M Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78-100, 1995. Google Scholar
  3. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Low-diameter graph decomposition is in nc. In Scandinavian Workshop on Algorithm Theory, pages 83-93. Springer, 1992. Google Scholar
  4. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 184-193. IEEE, 1996. Google Scholar
  5. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In International Symposium on Distributed Computing, 2017. Google Scholar
  6. Guy E Blelloch, Anupam Gupta, Ioannis Koutis, Gary L Miller, Richard Peng, and Kanat Tangwongsan. Nearly-linear work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs. Theory of Computing Systems, 55(3):521-554, 2014. Google Scholar
  7. Michael Elkin and Ofer Neiman. Distributed strong diameter network decomposition. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 211-216. ACM, 2016. Google Scholar
  8. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks ii: Low-congestion shortcuts, mst, and min-cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 202-219. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  9. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 451-460. ACM, 2016. Google Scholar
  10. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In International Symposium on Distributed Computing, pages 158-172. Springer, 2016. Google Scholar
  11. Bernhard Haeupler, Goran Zuzic, and Jason Li. Low-congestion shortcuts for any minor closed family. In personal communications, 2017. Google Scholar
  12. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. An almost-tight distributed algorithm for computing single-source shortest paths. In Proceedings of the ACM Symposium on Theory of Computing, 2016. Google Scholar
  13. Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 238-251. ACM, 1995. Google Scholar
  14. Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 153-162. ACM, 2015. Google Scholar
  15. Nathan Linial and Michael E Saks. Decomposing graphs into regions of small diameter. In SODA, volume 91, pages 320-330, 1991. Google Scholar
  16. Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, pages 196-203. ACM, 2013. Google Scholar
  17. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the ACM Symposium on Theory of Computing, pages 565-573, 2014. Google Scholar
  18. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing, pages 439-453. Springer, 2014. Google Scholar
  19. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail