In the k-Disjoint Shortest Paths problem, a set of source terminal pairs of vertices \{(s_i,t_i)\mid 1\le i\le k\} is given and we are asked to find paths P_1,\ldots,P_k such that each path P_i is a shortest path from s_i to t_i and every vertex of the graph routes at most one of such paths . We introduce a relaxation of the problem, namely, k-Disjonit Shortest Paths with Congestion-c where every vertex is allowed to route up to c paths. We provide a simple algorithm to solve the k-Disjonit Shortest Paths with Congestion-c problem in time f(k) n^{O(k-c)} on DAGs. Our algorithm is based on the earlier algorithm for k-Disjonit Paths with Congestion-c[ IPL 2019, MFCS 2016 ], but we significantly simplify their argument. We also discuss the hardness of the problem , achieving a better lower bound than the previous one [ IPL 2019 ] . We believe our simplified method of analysis can be helpful to deal with similar problems on general undirected graphs .
In the k-Disjoint Shortest Paths problem, a set of terminal pairs of vertices \{(s_i,t_i)\mid 1\le i\le k\} is given and we are asked to find paths P_1,\ldots,P_k such that each path P_i is a shortest path from s_i to t_i and every vertex of the graph routes at most one of them . We introduce a generalization of the problem, namely, k-Disjoint Shortest Paths with Congestion-c where every vertex is allowed to route up to c paths. We provide a simple algorithm to solve the problem in time f(k) n^{O(k-c)} on DAGs. Using the techniques for DAGs, we show the problem is solvable in time f(k) n^{O(k) is based on the earlier algorithm for k-Disjoint Paths with Congestion-c[ IPL2019 ], but we significantly simplify their argument. Then we prove that it is not possible to improve the algorithm significantly by showing that for every constant c the problem is W [ 1 ] -hard w.r.t.\ parameter k-c. We also consider the problem on acyclic planar graphs, but this time we restrict ourselves to the edge-disjoint shortest paths problem. We show that even on acyclic planar graphs there is no f(k)n^{o(k) .
D
source
R
such paths
them
R
relaxation
generalization
R
k-Disjonit
k-Disjoint
D
k-Disjonit Shortest Paths with Congestion-c
R
Our algorithm
Using the techniques for DAGs, we show the problem is solvable in time f(k) n^{O(k)
R
k-Disjonit
k-Disjoint
R
IPL 2019, MFCS 2016
IPL2019
R
We also discuss the hardness of the problem , achieving a better lower bound than the previous one
Then we prove that it is not possible to improve the algorithm significantly by showing that for every constant c the problem is W
R
IPL 2019
1
R
. We believe our simplified method of analysis can be helpful to deal with similar problems on general undirected graphs
-hard w.r.t.\ parameter k-c. We also consider the problem on acyclic planar graphs, but this time we restrict ourselves to the edge-disjoint shortest paths problem. We show that even on acyclic planar graphs there is no f(k)n^{o(k)