Document Open Access Logo

Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths

Authors Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.47.pdf
  • Filesize: 0.75 MB
  • 21 pages

Document Identifiers

Author Details

Timothy M. Chan
  • University of Illinois at Urbana-Champaign, IL, USA
Virginia Vassilevska Williams
  • MIT, CSAIL, Cambridge, MA, USA
Yinzhan Xu
  • MIT, Cambridge, MA, USA

Funding

  • Chan, Timothy M.: Supported by NSF Grant CCF-1814026.
  • Vassilevska Williams, Virginia: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.
  • Xu, Yinzhan: Supported by NSF Grant CCF-1528078.

Cite AsGet BibTex

Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 47:1-47:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.47

Abstract

All-Pairs Shortest Paths (APSP) is one of the most well studied problems in graph algorithms. This paper studies several variants of APSP in unweighted graphs or graphs with small integer weights. APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an Õ(n^ω) time algorithm, where ω < 2.373 is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be Ω(n^{2.5}) even if ω = 2 [Zwick'02]. To understand this n^{2.5} bottleneck, we build a web of reductions around directed unweighted APSP . We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of ω. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small (Õ(1)) integer weights, All-Pairs Longest Paths in DAGs with small weights, cRed-APSP in undirected graphs with small weights, for any c ≥ 2 (computing all-pairs shortest path distances among paths that use at most c red edges), #_{≤ c}APSP in directed graphs with small weights (counting the number of shortest paths for each vertex pair, up to c), and approximate APSP with additive error c in directed graphs with small weights, for c ≤ Õ(1). We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with {0,1} weights and #_{mod c}APSP in directed unweighted graphs (computing counts mod c), thus showing that unless the current algorithms for APSP in directed unweighted graphs can be improved substantially, these problems need at least Ω(n^{2.528}) time. We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights (previously studied by Zwick [STOC'99]) and for approximate APSP with sublinear additive error in directed unweighted graphs (previously studied by Roditty and Shapira [ICALP'08]). Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP (such as #_{≤ U}APSP and #_{mod U}APSP for U ≤ n^{Õ(1)}) in unweighted graphs, as well as a near-optimal Õ(n³)-time algorithm for the original #APSP problem in unweighted graphs (when counts may be exponentially large). This also implies an Õ(n³)-time algorithm for Betweenness Centrality, improving on the previous Õ(n⁴) running time for the problem. Our techniques also lead to a simpler alternative to Shoshan and Zwick’s algorithm [FOCS'99] for the original APSP problem in undirected graphs with small integer weights.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • All-Pairs Shortest Paths
  • Fine-Grained Complexity
  • Graph Algorithm

Metrics

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

Related Versions

References

  1. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. Google Scholar
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page to appear, 2021. Google Scholar
  3. 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. Google Scholar
  4. Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163-177, 2001. Google Scholar
  5. Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 943-954, 2019. Google Scholar
  6. Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39(5):2075-2089, 2010. URL: https://doi.org/10.1137/08071990X.
  7. Timothy M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Trans. Algorithms, 8(4):34:1-34:17, 2012. URL: https://doi.org/10.1145/2344422.2344424.
  8. Artur Czumaj, Miroslaw Kowaluk, and Andrzej Lingas. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci., 380(1-2):37-46, 2007. Google Scholar
  9. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 384-391, 2009. Google Scholar
  10. Michael J Fischer and Albert R Meyer. Boolean matrix multiplication and transitive closure. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT), pages 129-131, 1971. Google Scholar
  11. Zvi Galil and Oded Margalit. Witnesses for Boolean matrix multiplication and for transitive closure. J. Complex., 9(2):201-221, 1993. Google Scholar
  12. 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.
  13. Zvi Galil and Oded Margalit. All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci., 54(2):243-254, 1997. URL: https://doi.org/10.1006/jcss.1997.1385.
  14. Fabrizio Grandoni, Giuseppe F Italian, Aleksander Łukasiewicz, Nikos Parotsidis, and Przemysław Uznański. All-pairs lca in dags: Breaking through the o(n^2.5) barrier. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 273-289. SIAM, 2021. Google Scholar
  15. Karim Labib, Przemysław Uznański, and Daniel Wolleb-Graf. Hamming distance completeness. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 14:1-14:17, 2019. Google Scholar
  16. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296-303, 2014. Google Scholar
  17. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1029-1046, 2018. Google Scholar
  18. Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), pages 53:1-53:18, 2020. Google Scholar
  19. Jiří Matoušek. Computing dominances in Eⁿ. Inf. Process. Lett., 38(5):277-278, 1991. Google Scholar
  20. Liam Roditty and Asaf Shapira. All-pairs shortest paths with a sublinear additive error. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Part I, volume 5125 of Lecture Notes in Computer Science, pages 622-633. Springer, 2008. Google Scholar
  21. Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. Google Scholar
  22. Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 605-614, 1999. Google Scholar
  23. Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919-930. IEEE, 2020. Google Scholar
  24. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Part I, volume 4051 of Lecture Notes in Computer Science, pages 262-273, 2006. Google Scholar
  25. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 585-589, 2007. Google Scholar
  26. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms, 6(3):44:1-44:23, 2010. Google Scholar
  27. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), pages 887-898, 2012. Google Scholar
  28. Virginia Vassilevska Williams. Problem 2 on problem set 2 of CS367, October 15, 2015. URL: http://theory.stanford.edu/~virgi/cs367/hw2.pdf.
  29. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM), pages 3447-3487, 2018. Google Scholar
  30. Virginia Vassilevska Williams and Yinzhan Xu. Truly subcubic min-plus product for less structured matrices, with applications. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 12-29, 2020. Google Scholar
  31. R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965-1985, 2018. URL: https://doi.org/10.1137/15M1024524.
  32. Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 950-957, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496873.
  33. Uri Zwick. All pairs lightest shortest paths. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pages 61-69, 1999. Google Scholar
  34. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact