License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.13
URN: urn:nbn:de:0030-drops-78246
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7824/
 Go to the corresponding LIPIcs Volume Portal

### The Directed Disjoint Shortest Paths Problem

 pdf-format:

### Abstract

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.

### 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:1--13:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-049-1},
ISSN =	{1868-8969},
year =	{2017},
volume =	{87},
editor =	{Kirk Pruhs and Christian Sohler},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7824},
URN =		{urn:nbn:de:0030-drops-78246},
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

DROPS-Home | Fulltext Search | Imprint | Privacy