2023/07/24 by Schlotter, Ildikó
#05C38 (Secondary) #05C85 (Primary) 68W05 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2307.12602
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 → ℝ, 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, 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.