Shortest Two Disjoint Paths in Conservative Graphs

Abstract We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $$G=(V,E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> with edge weight function $${w:E\rightarrow \mathbb {R}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> <mml:mo>:</mml:mo> <mml:mi>E</mml:mi> <mml:mo>→</mml:mo> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> , 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -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 .