论文标题
局部到全球定理，用于拥挤的最短路径
A Local-to-Global Theorem for Congested Shortest Paths
论文作者
论文摘要
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 $。 我们将此定理扩展到一般图。对于无方向的图，我们证明相同的定理（在常数3中达到差异）。对于有向图，我们提供了定理（对于任何常数）的反例，并证明了该定理的往返类似物，该定理表明存在一对$（s，t）$的节点，以便$ g $中的每个节点都包含在最短的$ s $ st $ path的结合中，最短的$ ts $ ts $ - ts $ -path。 DAGS的原始定理具有$ k $的最高途径$ c $（（$ k，c $） - SPC）问题。在此问题中，我们将获得一个加权图$ g $，以及$ k $ node pairs $（s_1，t_1），\ dots，（s_k，t_k）$和一个正整数$ c \ leq k $。我们的任务是查找路径$ p_1，\ dots，p_k $，因此每个$ p_i $都是从$ s_i $到$ t_i $的最短路径，并且图中的每个节点最多都在$ c $ paths $ p_i $上，或者报告不存在这样的路径收集。 当$ c = k $独立找到每对$（s_i，t_i）$的最短路径时，可以轻松解决问题。当$ c = 1 $时，$（k，c）$ - spc问题恢复了$ k $ -dischint最短路径（$ k $ -dsp）问题，其中最短路径的收集必须是节点dischoint。对于固定的$ K $，可以在DAG和无方面的多项式时间内解决$ K $ -DSP。先前的工作表明，DAGS的本地到全球定理意味着每当$ k-c $是恒定的，$（k，c）$ -SPC在DAGS上。同样，我们的工作意味着$（k，c）$ -SPC可以在$ k-c $恒定的情况下以多项式图在多项式时间内解决。
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.
