S. Akhoondian Amiri
In the k-Disjoint Paths Problem, a set of terminal pairs of vertices $\{(s_i,t_i)| 1\le i\le k\}$ is given and we are asked to find disjoint paths $P_1,\ldots,P_k$ such that each path $P_i$ connects $s_i$ to $t_i$. There are two main variations of this problem: shortest disjoint paths and disjoint paths with congestion; in the former, the aim is to make each $P_i$ the shortest path and, in the latter, every vertex can tolerate a certain amount c of congestion.
We introduce a more natural problem by mixing the two: k-disjoint shortest paths with congestion-c. This problem is more realistic in the sense that in practical networks we can tolerate certain congestion, moreover, routing along short paths is in priority.
For this problem, we provide a simple algorithm to solve it in time $f(k) n^{O(k-c)}$ on DAGs.
Our algorithm is based on the earlier algorithm of Amiri et al.[IPL 2019], but we significantly simplify their proof argument. We also discuss the hardness of the problem, achieving a better lower bound than the existing one in the previous work.
We believe our simplified method of analysis can be helpful to deal with similar problems on general undirected graphs.
Keywords: Graph Algorithms, Disjoint Paths, Shortest Paths, Scheduling, Routing with Congestion, Acyclic Graphs
Scheduled
FA1 Graphs and Networks 1
June 11, 2021 9:15 AM
1 - GB Dantzig
