Document Open Access Logo

Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths

Authors Tomasz Kociumaka , Adam Polak

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.72.pdf
  • Filesize: 0.73 MB
  • 10 pages

Document Identifiers

Author Details

Tomasz Kociumaka
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Adam Polak
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Polak, Adam: Part of this work was done at École Polytechnique Fédérale de Lausanne, supported by the Swiss National Science Foundation projects Lattice Algorithms and Integer Programming (185030) and Complexity of Integer Programming (CRFS-2_207365).

Acknowledgements

The second author would like to thank Danupon Nanongkai and Luca Trevisan for bringing his attention to the problem discussed in this paper, Alexandra Lassota - for useful feedback on an early draft of the manuscript, and Imbir - a ginger tabby, who supervised initial stages of this work.

Cite AsGet BibTex

Tomasz Kociumaka and Adam Polak. Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 72:1-72:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.72

Abstract

This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman-Ford algorithm solves this problem in O(hm) time, where m is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with nonnegative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary h ∈ O(√m). Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction h ∈ O(√m). In other words, the O(hm) bound is tight for the entire space of parameters h, m, and n, where n is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • Fine-grained complexity
  • graph algorithms
  • lower bounds
  • shortest paths

Metrics

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

References

  1. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for subset sum and bicriteria path. ACM Trans. Algorithms, 18(1):6:1-6:22, 2022. URL: https://doi.org/10.1145/3450524.
  2. Anantaram Balakrishnan and Kemal Altinkemer. Using a hop-constrained model to generate alternative communication network design. INFORMS J. Comput., 4(2):192-205, 1992. URL: https://doi.org/10.1287/ijoc.4.2.192.
  3. Richard Bellman. Notes on the theory of dynamic programming IV - maximization over discrete sets. Naval Research Logistics Quarterly, 3(1-2):67-70, March 1956. URL: https://doi.org/10.1002/nav.3800030107.
  4. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958. URL: https://doi.org/10.1090/qam/102435.
  5. Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single-source shortest paths in near-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 600-611. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00063.
  6. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: https://doi.org/10.1007/s00453-012-9734-3.
  7. Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-weight single-source shortest paths in near-linear time: Now faster! In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE, 2023. URL: https://arxiv.org/abs/2304.05279.
  8. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 612-623. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00064.
  9. Shigang Chen and Klara Nahrstedt. An overview of quality of service routing for next-generation high-speed networks: problems and solutions. IEEE Netw., 12(6):64-79, 1998. URL: https://doi.org/10.1109/65.752646.
  10. Gang Cheng and Nirwan Ansari. Finding all hops shortest paths. IEEE Commun. Lett., 8(2):122-124, 2004. URL: https://doi.org/10.1109/LCOMM.2004.823365.
  11. Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. URL: https://doi.org/10.1145/3293465.
  12. Geir Dahl and Luis Eduardo Neves Gouveia. On the directed hop-constrained shortest path problem. Oper. Res. Lett., 32(1):15-22, 2004. URL: https://doi.org/10.1016/S0167-6377(03)00026-9.
  13. Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory, pages 129-131. IEEE Computer Society, 1971. URL: https://doi.org/10.1109/SWAT.1971.4.
  14. Lester Randolph Ford. Network flow theory. Technical report, RAND Corporation, 1956. URL: https://www.rand.org/pubs/papers/P923.html.
  15. Harold N. Gabow. Scaling algorithms for network problems. J. Comput. Syst. Sci., 31(2):148-168, 1985. URL: https://doi.org/10.1016/0022-0000(85)90039-X.
  16. Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for network problems. SIAM J. Comput., 18(5):1013-1036, 1989. URL: https://doi.org/10.1137/0218069.
  17. Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1208-1220. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451098.
  18. Andrew V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM J. Comput., 24(3):494-504, 1995. URL: https://doi.org/10.1137/S0097539792231179.
  19. Roch Guérin and Ariel Orda. Computing shortest paths for any number of hops. IEEE/ACM Trans. Netw., 10(5):613-620, 2002. URL: https://doi.org/10.1109/TNET.2002.803917.
  20. H. C. Joksch. The shortest route problem with constraints. Journal of Mathematical Analysis and Applications, 14(2):191-197, 1966. URL: https://doi.org/10.1016/0022-247X(66)90020-5.
  21. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.21.
  22. Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 of LIPIcs, pages 53:1-53:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.53.
  23. Jakub Łącki and Yasamin Nazari. Near-optimal decremental hopsets with applications. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, volume 229 of LIPIcs, pages 86:1-86:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.86.
  24. Alfonso Shimbel. Structure in communication nets. In Symposium on Information Networks, 1954, pages 199-203. Polytechnic Press of the Polytechnic Institute of Brooklyn, 1955. Google Scholar
  25. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pages 112-119. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060607.
  26. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In International Congress of Mathematicians, ICM 2018, pages 3447-3487, 2018. URL: https://doi.org/10.1142/9789813272880_0188.
  27. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  28. 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.
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