Abstract
Amiri and Wargalla proved the following localtoglobal theorem about shortest paths in directed acyclic graphs (DAGs): if G is a weighted DAG with the property 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 stpath 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). However, we prove a roundtrip analogue of the theorem which guarantees there exists a pair (s,t) of nodes such that every node in G is contained in the union of a shortest stpath and a shortest tspath.
The original localtoglobal theorem for DAGs has an application to the kShortest 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),… ,(s_k,t_k), and a positive integer c ≤ k, and tasked with finding a collection of paths P_1,… , 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, there are no congestion constraints, and the problem can be solved easily by running a shortest path algorithm for each pair (s_i,t_i) independently. At the other extreme, when c = 1, the (k,c)SPC problem is equivalent to the kDisjoint Shortest Paths (kDSP) problem, where the collection of shortest paths must be nodedisjoint. For fixed k, kDSP is polynomialtime solvable on DAGs and undirected graphs. Amiri and Wargalla interpolated between these two extreme values of c, to obtain an algorithm for (k,c)SPC on DAGs that runs in polynomial time when kc is constant.
In the same way, we prove that (k,c)SPC can be solved in polynomial time on undirected graphs whenever kc is constant. For directed graphs, because of our counterexample to the original theorem statement, our roundtrip localtoglobal result does not imply such an algorithm (k,c)SPC. Even without an algorithmic application, our proof for directed graphs may be of broader interest because it characterizes intriguing structural properties of shortest paths in directed graphs.
BibTeX  Entry
@InProceedings{akmal_et_al:LIPIcs.ESA.2023.8,
author = {Akmal, Shyan and Wein, Nicole},
title = {{A LocalToGlobal Theorem for Congested Shortest Paths}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {8:18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18661},
URN = {urn:nbn:de:0030drops186618},
doi = {10.4230/LIPIcs.ESA.2023.8},
annote = {Keywords: disjoint paths, shortest paths, congestion, parameterized complexity}
}
Keywords: 

disjoint paths, shortest paths, congestion, parameterized complexity 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 