Shortest Two Disjoint Paths in Conservative Graphs

Schlotter, Ildikó Anna (2026) Shortest Two Disjoint Paths in Conservative Graphs. ALGORITHMICA, 88 (2). No. 31. ISSN 0178-4617

Preview

Text s00453-026-01375-7.pdf - Published Version Available under License Creative Commons Attribution. Download (940kB) | Preview

Abstract

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G=(V,E) G = ( V , E ) with edge weight function {w:E\rightarrow \mathbb {R}} 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 \textsf{NP} 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 .

Actions (login required)

Edit Item