摘要：In the k disjoint shortest paths problem (k-DSPP), 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 (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2-DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by Eilam-Tzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2-DSPP 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-DSPP 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-DSPP and the vertex-disjoint version of the directed k-DSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant.
关键词：Disjoint paths; shortest path; polynomial time algorithm
