2026-07-22T21:35:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17332 2024-03-06T10:59:29Z ddc:004 open_access

One-Face Shortest Disjoint Paths with a Deviation Terminal Kobayashi, Yusuke Terao, Tatsuya shortest disjoint paths polynomial time algorithm planar graph For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yusuke Kobayashi and Tatsuya Terao 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.47 urn:nbn:de:0030-drops-173322 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.47 eng https://creativecommons.org/licenses/by/4.0/legalcode