A Local-to-Global Theorem for Congested Shortest Paths
share
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),…,(s_k,t_k), and a positive integer c≤ k. We are tasked with finding 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 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.
READ FULL TEXT