|
In the k disjoint shortest paths problem, we are given a graph and its vertex pairs $(s_1, t_1),...,(s_k,t_k)$, and the objective is to find k pairwise disjoint paths $P_1,...,P_k$ such that each path $P_i$ is a shortest path from $s_i$ to $t_i$, if they exist. If the length of each edge is equal to zero, then this problem amounts to the disjoint paths problem, which is one of the well-studied problems in algorithmic graph theory and combinatorial optimization. Eilam-Tzoreff focused on the case when the length of each edge is positive, and showed that the undirected version of the 2 disjoint shortest paths problem can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem. In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of the 2 Disjoint Shortest Paths Problem when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NP-hard, which implies that the directed 2 disjoint shortest paths problem is NP-hard if the length of each edge can be zero. We extend our result to the case when the instance has two terminal pairs and the number of paths is a fixed constant greater than two. We also show that the undirected k disjoint shortest paths problem and the vertex- disjoint version of the directed k disjoint shortest paths problem can be solved in polynomial time if the input graph is planar and k is a fixed constant.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Kobayashi, Yusuke}, |
| TITLE | = | {The directed disjoint shortest paths problem}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-13} |