Shortest Two Disjoint Paths in Conservative Graphs

Schlotter, Ildikó Anna (2024) Shortest Two Disjoint Paths in Conservative Graphs. In: 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024. Leibniz International Proceedings in Informatics, LIPIcs (289). Leibniz-Zentrum für Informatik, Wadern, No. 57. ISBN 9783959773119

Preview

Text LIPIcs.STACS.2024.57.pdf - Published Version Available under License Creative Commons Attribution. Download (903kB) | Preview

Abstract

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = (V, E) with edge weights w : E → R, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G. © Ildikó Schlotter; licensed under Creative Commons License CC-BY 4.0.

Actions (login required)

Edit Item