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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7824/
Go to the corresponding LIPIcs Volume Portal

Berczi, Kristof ; Kobayashi, Yusuke

The Directed Disjoint Shortest Paths Problem

pdf-format:
LIPIcs-ESA-2017-13.pdf (0.5 MB)

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 Published by LZI