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
