2026-07-25T15:15:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7824 2024-03-06T10:41:16Z ddc:004 open_access

The Directed Disjoint Shortest Paths Problem Berczi, Kristof Kobayashi, Yusuke Disjoint paths shortest path polynomial time algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristof Berczi and Yusuke Kobayashi 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.13 urn:nbn:de:0030-drops-78246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.13 eng https://creativecommons.org/licenses/by/3.0/legalcode