Min-sum two edge-disjoint paths

From Egres Open
Jump to: navigation, search

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 [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


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