2026-07-23T08:19:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14095 2024-03-06T10:53:27Z ddc:004 open_access

Using a Geometric Lens to Find k Disjoint Shortest Paths Bentert, Matthias Nichterlein, André Renken, Malte Zschoche, Philipp graph algorithms dynamic programming W[1]-hardness geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and André Nichterlein and Malte Renken and Philipp Zschoche 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.26 urn:nbn:de:0030-drops-140954 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.26 eng https://creativecommons.org/licenses/by/4.0/legalcode