LIPIcs.ICALP.2021.26.pdf
- Filesize: 0.9 MB
- 14 pages
Document
Using a Geometric Lens to Find k Disjoint Shortest Paths
Authors
André Nichterlein 
,
Malte Renken ,
Philipp Zschoche
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
File
Document Identifiers
Author Details
- Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
- Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Cite As Get BibTex
Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.26
Abstract
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1,t_1), …, (s_k,t_k), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_1, …, P_k such that P_i is a shortest s_i-t_i-path for each i ∈ [k]. Recently, Lochet [SODA '21] provided an algorithm that solves k-DSP in n^{O(k^{5^k})} time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(kn^{16k ⋅ k! + k + 1})-time algorithm based on a novel geometric view on this problem. For the special case k = 2, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- graph algorithms
- dynamic programming
- W[1]-hardness
- geometry
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Maxim Akhmedov. Faster 2-disjoint-shortest-paths algorithm. In Proceedings of the 15th International Computer Science Symposium in Russia (CSR '20), volume 12159 of Lecture Notes in Computer Science, pages 103-116. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-50026-9_7.
- Kristof Berczi and Yusuke Kobayashi. The Directed Disjoint Shortest Paths Problem. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA '17), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.13.
- Andreas Björklund and Thore Husfeldt. Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), volume 123 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.19.
- Andreas Björklund and Thore Husfeldt. Shortest two disjoint paths in polynomial time. SIAM Journal on Computing, 48(6):1698-1710, 2019. URL: https://doi.org/10.1137/18M1223034.
- Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics, 85(2):113-138, 1998. URL: https://doi.org/10.1016/S0166-218X(97)00121-2.
- Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Meirav Zehavi. New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). Dagstuhl Reports, 9(1):67-87, 2019. URL: https://doi.org/10.4230/DagRep.9.1.67.
- Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111-121, 1980. URL: https://doi.org/10.1016/0304-3975(80)90009-2.
- Marinus Gottschau, Marcus Kaiser, and Clara Waldmann. The undirected two disjoint shortest paths problem. Operations Research Letters, 47(1):70-75, 2019. URL: https://doi.org/10.1016/j.orl.2018.11.011.
- Richard M Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45-68, 1975. URL: https://doi.org/10.1002/net.1975.5.1.45.
- Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory. Series B, 102(2):424-435, 2012. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
- Yusuke Kobayashi and Ryo Sako. Two disjoint shortest paths problem with non-negative edge length. Operations Research Letters, 47(1):66-69, 2019. URL: https://doi.org/10.1016/j.orl.2018.11.012.
- William Lochet. A polynomial time algorithm for the k-disjoint shortest paths problem. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21), pages 169-178. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.12.
- Neil Robertson and Paul D. Seymour. Graph minors. XIII: the disjoint paths problem. Journal of Combinatorial Theory. Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
- Torsten Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Compututer Science, 465:35-48, 2012. URL: https://doi.org/10.1016/j.tcs.2012.09.025.