Computer Science > Data Structures and Algorithms
[Submitted on 13 Nov 2022 (v1), last revised 27 Jun 2023 (this version, v2)]
Title:A Local-to-Global Theorem for Congested Shortest Paths
View PDFAbstract: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.
Submission history
From: Nicole Wein [view email][v1] Sun, 13 Nov 2022 23:08:27 UTC (90 KB)
[v2] Tue, 27 Jun 2023 23:32:38 UTC (1,767 KB)
Current browse context:
cs.DS
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.