# Min-sum two edge-disjoint paths

Let *G=(V,E)* be an undirected graph and let [math](s_1,t_1), (s_2,t_2)[/math] be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disjoint [math]s_1-t_1[/math] and [math]s_2-t_2[/math] paths with minimum total length.

## Remarks

A randomized polynomial-time algorithm for the problem was given by Björklund and Husfeldt ^{[1]}, based on algebraic methods. This works for both the vertex-disjoint and the edge-disjoint versions. For the vertex-disjoint problem in planar graphs, there is an algorithm by Kobayashi and Sommer ^{[2]} for the case when all four terminals are incident to two faces.

Eilam-Tzoreff ^{[3]} gave a polynomial-time algorithm for the easier problem of deciding whether there are edge-disjoint [math]s_1-t_1[/math] and [math]s_2-t_2[/math] paths which are both shortest path in *G*.

The randomized algorithm of Björklund and Husfeldt has been generalized to the following problem by Hirai and Namba ^{[4]}: given two disjoint node sets *A* and *B*, both of even cardinality and *|A|+|B|* fixed, find *|A|/2+|B|/2* disjoint path of minimum total length such that each path has both endpoints either in *A* or in *B*. The problem is NP-complete if *|A|+|B|* is not fixed.

## Related problems

Orientation with shortest round trip

## References

- ↑ A. Björklund, T. Husfeldt,
*Shortest Two Disjoint Paths in Polynomial Time*, DOI link, author link - ↑ Y. Kobayashi, C. Sommer,
*On shortest disjoint paths in planar graphs*, DOI link, author link - ↑ T. Eilam-Tzoreff,
*The disjoint shortest paths problem*, DOI link - ↑ H. Hirai, H. Namba,
*Shortest (A+B)-path packing via hafnian*, arXiv link