Document Open Access Logo

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Authors Michael Elkin, Ofer Neiman

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2022.27.pdf
  • Filesize: 0.78 MB
  • 22 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • Shortest paths
  • matrix multiplication
  • hopsets

Metrics

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

Abstract

Consider an undirected weighted graph G = (V,E,w). We study the problem of computing (1+ε)-approximate shortest paths for S × V, for a subset S ⊆ V of |S| = n^r sources, for some 0 < r ≤ 1. We devise a significantly improved algorithm for this problem in the entire range of parameter r, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of r in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time Õ(|E| ⋅ n^{o(1)} + n^{ω(r)}), where n^{ω(r)} is the time required to multiply an n^r × n matrix by an n × n one. Our PRAM algorithm has polylogarithmic time (log n)^{O(1/ρ)}, and its work complexity is Õ(|E| ⋅ n^ρ + n^{ω(r)}), for any arbitrarily small constant ρ > 0.
In particular, for r ≤ 0.313…, our centralized algorithm computes S × V (1+ε)-approximate shortest paths in n^{2 + o(1)} time. Our PRAM polylogarithmic-time algorithm has work complexity O(|E| ⋅ n^ρ + n^{2+o(1)}), for any arbitrarily small constant ρ > 0. Previously existing solutions either require centralized time/parallel work of O(|E| ⋅ |S|) or provide much weaker approximation guarantees.
In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for |S| = n^r sources, for r ≤ 0.655, while previous state-of-the-art algorithms did so only for r ≤ 1/2. Moreover, it improves previous bounds for all r > 1/2. For unweighted graphs, the running time is improved further to poly(log log n) for r ≤ 0.655. Previously this running time was known for r ≤ 1/2.

Cite As Get BibTex

Michael Elkin and Ofer Neiman. Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.27

Author Details

Michael Elkin
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Ofer Neiman
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

  • Elkin, Michael: Funded by ISF grant 2344/19.
  • Neiman, Ofer: Funded by ISF grant 1817/17.

Acknowledgements

We are grateful to François Le Gall for explaining us certain aspects of the algorithm of [Francois Le Gall and Florent Urrutia, 2018], and to Shaked Matar for helpful discussions.

References

  1. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  2. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci., 54(2):255-262, 1997. URL: https://doi.org/10.1006/jcss.1997.1388.
  3. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In STOC, 2020. Google Scholar
  4. S. Baswana and S. Sen. A simple linear time algorithm for computing a (2k-1)-spanner of O(n^1+1/k) size in weighted graphs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719 of LNCS, pages 384-396. Springer, 2003. Google Scholar
  5. Surender Baswana and Telikepalli Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In FOCS, pages 591-602, 2006. URL: https://doi.org/10.1109/FOCS.2006.29.
  6. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 7:1-7:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.7.
  7. Aaron Bernstein. Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 693-702, 2009. URL: https://doi.org/10.1109/FOCS.2009.16.
  8. Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. SIAM J. Discret. Math., 19(4):1029-1055, 2005. URL: https://doi.org/10.1137/S0895480103431046.
  9. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 74-83. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331633.
  10. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 143-152, 2015. Google Scholar
  11. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47(1):132-166, 2000. URL: https://doi.org/10.1145/331605.331610.
  12. Edith Cohen and Uri Zwick. All-pairs small-stretch paths. J. Algorithms, 38(2):335-353, 2001. URL: https://doi.org/10.1006/jagm.2000.1117.
  13. Don Coppersmith. Rectangular matrix multiplication revisited. J. Complex., 13(1):42-49, 1997. URL: https://doi.org/10.1006/jcom.1997.0438.
  14. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. URL: https://doi.org/10.1016/S0747-7171(08)80013-2.
  15. D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM J. Comput., 29:1740-1759, 2000. Google Scholar
  16. Michal Dory and Merav Parter. Exponentially faster shortest paths in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 59-68, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405711.
  17. M. Elkin. Computing almost shortest paths. In Proc. 20th ACM Symp. on Principles of Distributed Computing, pages 53-62, 2001. Google Scholar
  18. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost shortest paths and PRAM distance oracles in weighted graphs. CoRR, abs/1907.11422, 2019. URL: http://arxiv.org/abs/1907.11422.
  19. Michael Elkin and Shaked Matar. Deterministic PRAM approximate shortest paths in polylogarithmic time and slightly super-linear work. In Kunal Agrawal and Yossi Azar, editors, SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 198-207. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461809.
  20. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM J. Comput., 48(4):1436-1480, 2019. URL: https://doi.org/10.1137/18M1166791.
  21. Michael Elkin and Ofer Neiman. Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019., pages 333-341, 2019. URL: https://doi.org/10.1145/3323165.3323177.
  22. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: https://doi.org/10.1145/28869.28874.
  23. Zvi Galil and Oded Margalit. Witnesses for boolean matrix multiplication and for transitive closure. J. Complex., 9(2):201-221, 1993. URL: https://doi.org/10.1006/jcom.1993.1014.
  24. Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Inf. Comput., 134(2):103-139, 1997. URL: https://doi.org/10.1006/inco.1997.2620.
  25. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  26. François Le Gall. Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 57-70. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_5.
  27. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1029-1046. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.67.
  28. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 146-155, 2014. URL: https://doi.org/10.1109/FOCS.2014.24.
  29. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 489-498, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897638.
  30. Xiaohan Huang and Victor Y. Pan. Fast rectangular matrix multiplication and applications. J. Complex., 14(2):257-299, 1998. URL: https://doi.org/10.1006/jcom.1998.0476.
  31. Philip N. Klein and Sairam Subramanian. A linear-processor polylog-time algorithm for shortest paths in planar graphs. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 259-270, 1993. URL: https://doi.org/10.1109/SFCS.1993.366861.
  32. Philip N. Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25(2):205-220, 1997. URL: https://doi.org/10.1006/jagm.1997.0888.
  33. Jason Li. Faster parallel algorithm for approximate shortest path. In STOC, 2020. Google Scholar
  34. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 565-573, 2014. URL: https://doi.org/10.1145/2591796.2591850.
  35. Yossi Shiloach and Uzi Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms, 2(1):88-102, 1981. URL: https://doi.org/10.1016/0196-6774(81)90010-9.
  36. Mikkel Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci., 69(3):330-353, 2004. URL: https://doi.org/10.1016/j.jcss.2004.04.003.
  37. Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J. Comput., 20(1):100-125, 1991. URL: https://doi.org/10.1137/0220006.
  38. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  39. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Trans. Algorithms, 1(1):2-13, 2005. URL: https://doi.org/10.1145/1077464.1077466.
  40. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. URL: https://doi.org/10.1145/567112.567114.
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact