# Using a geometric lens to find k disjoint shortest paths

Preprint · Matthias Bentert, André Nichterlein, Malte Renken, Philipp Zschoche

- Archive id: arxiv:2007.12502
- Published: 2020-07-24
- DOI: https://doi.org/10.4230/lipics.icalp.2021.26
- arXiv: https://arxiv.org/abs/2007.12502
- Source URL: https://arxiv.org/abs/2007.12502
- PDF: https://arxiv.org/pdf/2007.12502
- Provenance: arxiv

## Abstract

Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s\_1,t\_1), \\ldots, (s\_k,t\_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P\_1,\\ldots, P\_k$ such that $P\_i$ is a shortest $s\_i$-$t\_i$-path for each $i \\in \[k\]$. Recently, Lochet \[SODA 2021\] 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 $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.