Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bentert, Matthias; Nichterlein, André; Renken, Malte; Zschoche, Philipp https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-140954
URL:

; ; ;

Using a Geometric Lens to Find k Disjoint Shortest Paths

pdf-format:


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
Seminar: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue date: 2021
Date of publication: 02.07.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI