# Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Preprint · Rajesh Chitnis, Samuel Thomas, Anthony Wirth

- Archive id: arxiv:2408.03933
- Published: 2024-08-07
- arXiv: https://arxiv.org/abs/2408.03933
- Source URL: https://arxiv.org/abs/2408.03933
- PDF: https://arxiv.org/pdf/2408.03933
- Provenance: arxiv

## Abstract

Given a graph $G=(V,E)$ and a set $T=\\{ (s\_i, t\_i) : 1\\leq i\\leq k \\}\\subseteq V\\times V$ of $k$ pairs, the $k$-vertex-disjoint-paths (resp. $k$-edge-disjoint-paths) problem asks to determine whether there exist~$k$ pairwise vertex-disjoint (resp. edge-disjoint) paths $P\_1, P\_2, ..., P\_k$ in $G$ such that, for each $1\\leq i\\leq k$, $P\_i$ connects $s\_i$ to $t\_i$. Both the edge-disjoint and vertex-disjoint versions in undirected graphs are famously known to be FPT (parameterized by $k$) due to the Graph Minor Theory of Robertson and Seymour. Eilam-Tzoreff \[DAM \`98\] introduced a variant, known as the $k$-disjoint-shortest-paths problem, where each individual path is further required to be a shortest path connecting its pair. They showed that the $k$-disjoint-shortest-paths problem is NP-complete on both directed and undirected graphs; this holds even if the graphs are planar and have unit edge lengths. We focus on four versions of the problem, corresponding to considering edge/vertex disjointness, and to considering directed/undirected graphs. Building on the reduction of Chitnis \[SIDMA \`23\] for $k$-edge-disjoint-paths on planar DAGs, we obtain the following inapproximability lower bound for each of the four versions of $k$-disjoint-shortest-paths on $n$-vertex graphs: - Under Gap-ETH, there exists a constant $δ\>0$ such that for any constant $0\<ε\\leq \\frac{1}{2}$ and any computable function $f$, there is no $(\\frac{1}{2}+ε)$-approx in $f(k)\\cdot n^{δ\\cdot k}$ time. We further strengthen our results as follows: Directed: Inapprox lower bound for edge-disjoint (resp. vertex-disjoint) paths holds even if the input graph is a planar (resp. 1-planar) DAG with max in-degree and max out-degree at most $2$. Undirected: Inapprox lower bound for edge-disjoint (resp. vertex-disjoint) paths hold even if the input graph is planar (resp. 1-planar) and has max degree $4$.

_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.