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.
A randomized polynomial-time algorithm for the problem was given by Björklund and Husfeldt , 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  for the case when all four terminals are incident to two faces.
Eilam-Tzoreff  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 : 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.
- 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