In the k-Vertex 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 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. 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.
R
k-Vertex Disjoint
k-Disjoint
A
source