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. In this work 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. Along this way, we significantly simplify the argument that is used in the previous work for k-Disjoint Paths with Congestion-c by Amiri et al  . We also discuss the hardness of problem and open problems in this area ] .
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 .
R
In this work we
We
R
Along this way, we significantly simplify the argument that is used in the previous work for k-Disjoint
Our algorithm is based on the earlier algorithm for k-Disjonit
R
by Amiri et al
IPL 2019, MFCS 2016
A
, but we significantly simplify their argument
R
problem and open problems in this area
the problem, achieving a better lower bound than the previous one
A
IPL 2019
A
. We believe our simplified method of analysis can be helpful to deal with similar problems on general undirected graphs