Document Open Access Logo

Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths

Authors Stefan Kratsch , Florian Nelles

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.38.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Stefan Kratsch
  • Humboldt-Universität zu Berlin, Germany
Florian Nelles
  • Humboldt-Universität zu Berlin, Germany

Cite AsGet BibTex

Stefan Kratsch and Florian Nelles. Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.38

Abstract

Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the ?(n³) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time ?(n^2.842), but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving ALL-PAIRS SHORTEST PATHS. We obtain efficient (and combinatorial) parameterized algorithms on non-negative vertex-weighted graphs of times ?(cw²n²), resp. ?(mw²n + n²). If fast matrix multiplication is allowed then the latter can be improved to ?(mw^{1.842} n + n²) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and they outperform them already for mw ∈ ?(n^{1 - ε}) for any ε > 0.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • All-pairs shortest Paths
  • efficient parameterized Algorithms
  • parameterized Complexity
  • Clique-width
  • Modular-width

Metrics

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

Related Versions

References

  1. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. J. Comput. Syst. Sci., 103:61-77, 2019. URL: https://doi.org/10.1016/j.jcss.2019.02.004.
  2. Matthias Bentert and André Nichterlein. Parameterized complexity of diameter. In Pinar Heggernes, editor, Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings, volume 11485 of Lecture Notes in Computer Science, pages 50-61. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17402-6_5.
  3. 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.
  4. David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. 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 2765-2784. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.176.
  5. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  6. Artur Czumaj and Andrzej Lingas. Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput., 39(2):431-444, 2009. URL: https://doi.org/10.1137/070695149.
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Trans. Algorithms, 14(3):34:1-34:45, 2018. URL: https://doi.org/10.1145/3186898.
  10. Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):83-89, 1976. URL: https://doi.org/10.1137/0205006.
  11. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. CoRR, abs/1506.01652, 2015. URL: http://arxiv.org/abs/1506.01652.
  12. Yijie Han and Tadao Takaoka. An ?(n³ log log n/ log² n) time algorithm for all pairs shortest paths. J. Discrete Algorithms, 38-41:9-19, 2016. URL: https://doi.org/10.1016/j.jda.2016.09.001.
  13. Thore Husfeldt. Computing graph distances parameterized by treewidth and diameter. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 16:1-16:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.16.
  14. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the power of tree-depth for fully polynomial FPT algorithms. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 41:1-41:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.41.
  15. jvind Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition-relationships and results for random graphs. In Congr. Numer. Citeseer, 1998. Google Scholar
  16. Stefan Kratsch and Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.55.
  17. Stefan Kratsch and Florian Nelles. Efficient parameterized algorithms for computing all-pairs shortest paths. arXiv e-prints, page arXiv:2001.04908, January 2020. URL: http://arxiv.org/abs/2001.04908.
  18. Andrzej Lingas and Dzmitry Sledneu. A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs. In Mária Bieliková, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser, and György Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012. Proceedings, volume 7147 of Lecture Notes in Computer Science, pages 373-384. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27660-6_31.
  19. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Fine-grained algorithm design for matching. CoRR, abs/1609.08879, 2016. URL: http://arxiv.org/abs/1609.08879.
  20. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312(1):47-74, 2004. Google Scholar
  21. Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing, 34(6):1398-1431, 2005. Google Scholar
  22. Asaf Shapira, Raphael Yuster, and Uri Zwick. All-pairs bottleneck paths in vertex weighted graphs. Algorithmica, 59(4):621-633, 2011. URL: https://doi.org/10.1007/s00453-009-9328-x.
  23. Susmita Susmita and Manish Pandey. Algorithms of all pair shortest path problem. International Journal of Computer Applications, 120(15):1-6, 2015. Google Scholar
  24. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 634-645. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_52.
  25. Egon Wanke. k-NLC graphs and polynomial algorithms. Discrete Applied Mathematics, 54(2-3):251-266, 1994. URL: https://doi.org/10.1016/0166-218X(94)90026-4.
  26. Stephen Warshall. A theorem on boolean matrices. In Journal of the ACM. Citeseer, 1962. Google Scholar
  27. 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.
  28. 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.
  29. Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 950-957. SIAM, 2009. URL: https://doi.org/10.1137/1.9781611973068.
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