Abstract
In the k disjoint shortest paths problem (kDSPP), 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 wellstudied problems in algorithmic graph theory and combinatorial optimization. EilamTzoreff (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by EilamTzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2DSPP when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NPhard, which implies that the directed 2DSPP is NPhard 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 kDSPP and the vertexdisjoint version of the directed kDSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant.
BibTeX  Entry
@InProceedings{berczi_et_al:LIPIcs:2017:7824,
author = {Kristof Berczi and Yusuke Kobayashi},
title = {{The Directed Disjoint Shortest Paths Problem}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {13:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7824},
URN = {urn:nbn:de:0030drops78246},
doi = {10.4230/LIPIcs.ESA.2017.13},
annote = {Keywords: Disjoint paths, shortest path, polynomial time algorithm}
}
Keywords: 

Disjoint paths, shortest path, polynomial time algorithm 
Collection: 

25th Annual European Symposium on Algorithms (ESA 2017) 
Issue Date: 

2017 
Date of publication: 

01.09.2017 