License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.26
URN: urn:nbn:de:0030-drops-140954
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14095/
Bentert, Matthias ;
Nichterlein, André ;
Renken, Malte ;
Zschoche, Philipp
Using a Geometric Lens to Find k Disjoint Shortest Paths
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.
BibTeX - Entry
@InProceedings{bentert_et_al:LIPIcs.ICALP.2021.26,
author = {Bentert, Matthias and Nichterlein, Andr\'{e} and Renken, Malte and Zschoche, Philipp},
title = {{Using a Geometric Lens to Find k Disjoint Shortest Paths}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {26:1--26:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14095},
URN = {urn:nbn:de:0030-drops-140954},
doi = {10.4230/LIPIcs.ICALP.2021.26},
annote = {Keywords: graph algorithms, dynamic programming, W\lbrack1\rbrack-hardness, geometry}
}
|
Keywords: |
|
graph algorithms, dynamic programming, W[1]-hardness, geometry |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
