# A Local-to-Global Theorem for Congested Shortest Paths

Article · Shyan Akmal, Nicole Wein

- Archive id: arxiv:2211.07042
- Published: 2022-11-13
- DOI: https://doi.org/10.4230/lipics.esa.2023.8
- arXiv: https://arxiv.org/abs/2211.07042
- Citations: 1
- Source URL: https://arxiv.org/abs/2211.07042
- PDF: https://arxiv.org/pdf/2211.07042
- Provenance: arxiv

## Abstract

Amiri and Wargalla (2020) proved the following local-to-global theorem in directed acyclic graphs (DAGs): if $G$ is a weighted DAG such that for each subset $S$ of 3 nodes there is a shortest path containing every node in $S$, then there exists a pair $(s,t)$ of nodes such that there is a shortest $st$-path containing every node in $G$. We extend this theorem to general graphs. For undirected graphs, we prove that the same theorem holds (up to a difference in the constant 3). For directed graphs, we provide a counterexample to the theorem (for any constant), and prove a roundtrip analogue of the theorem which shows there exists a pair $(s,t)$ of nodes such that every node in $G$ is contained in the union of a shortest $st$-path and a shortest $ts$-path. The original theorem for DAGs has an application to the $k$-Shortest Paths with Congestion $c$ (($k,c$)-SPC) problem. In this problem, we are given a weighted graph $G$, together with $k$ node pairs $(s\_1,t\_1),\\dots,(s\_k,t\_k)$, and a positive integer $c\\leq k$. We are tasked with finding paths $P\_1,\\dots, P\_k$ such that each $P\_i$ is a shortest path from $s\_i$ to $t\_i$, and every node in the graph is on at most $c$ paths $P\_i$, or reporting that no such collection of paths exists. When $c=k$ the problem is easily solved by finding shortest paths for each pair $(s\_i,t\_i)$ independently. When $c=1$, the $(k,c)$-SPC problem recovers the $k$-Disjoint Shortest Paths ($k$-DSP) problem, where the collection of shortest paths must be node-disjoint. For fixed $k$, $k$-DSP can be solved in polynomial time on DAGs and undirected graphs. Previous work shows that the local-to-global theorem for DAGs implies that $(k,c)$-SPC on DAGs whenever $k-c$ is constant. In the same way, our work implies that $(k,c)$-SPC can be solved in polynomial time on undirected graphs whenever $k-c$ is constant.

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