# Disjoint Shortest Paths with Congestion on DAGs

Preprint · Saeed Akhoondian Amiri, Julian Wargalla

- Archive id: arxiv:2008.08368
- Published: 2020-08-19
- arXiv: https://arxiv.org/abs/2008.08368
- Citations: 0
- Source URL: https://arxiv.org/abs/2008.08368
- PDF: https://arxiv.org/pdf/2008.08368
- Provenance: arxiv

## Abstract

In the k-Disjoint Shortest Paths problem, a set of terminal pairs of vertices $\\{(s\_i,t\_i)\\mid 1\\le i\\le k\\}$ is given and we are asked to find paths $P\_1,\\ldots,P\_k$ such that each path $P\_i$ is a shortest path from $s\_i$ to $t\_i$ and every vertex of the graph routes at most one of them. We introduce a generalization of the problem, namely, $k$-Disjoint Shortest Paths with Congestion-$c$ where every vertex is allowed to route up to $c$ paths. We provide a simple algorithm to solve the problem in time $f(k) n^{O(k-c)}$ on DAGs. Using the techniques for DAGs, we show the problem is solvable in time $f(k) n^{O(k)}$ on general undirected graphs. Our algorithm for DAGs is based on the earlier algorithm for $k$-Disjoint Paths with Congestion-$c$\[IPL2019\], but we significantly simplify their argument. Then we prove that it is not possible to improve the algorithm significantly by showing that for every constant $c$ the problem is W\[1\]-hard w.r.t.\\ parameter $k-c$. We also consider the problem on acyclic planar graphs, but this time we restrict ourselves to the edge-disjoint shortest paths problem. We show that even on acyclic planar graphs there is no $f(k)n^{o(k)}$ algorithm for the problem unless ETH fails.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

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