4

In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed $k\in \mathbb{N}$.

Suppose now that we are trying to find $k$-disjoint-paths, such that the sum of their lengths is minimal.

Related results:

  • Using a similar reduction to the one I proposed here, it is possible to show that if there's a single source (and $k$ targets), the problem is in $P$.

  • There's a known algorithm(with the unusual runtime of $O(|V|^8)$) for a related problem, where only shortest $s_i\to t_i$ paths are to be considered. In this variant, $k=2$ is in $P$ .

  • In the same paper, they state that (notice it's not the same problem):

    "the complexity for fixed $k \geq 3$ remains an open problem. "

What can we say about the "short-$k$-disjoint-paths" problem?

R B
  • 9,448
  • 5
  • 34
  • 74

1 Answers1

8

We just answered this for $k=2$:

Andreas Björklund and Thore Husfeldt, Shortest two disjoint paths in polynomial time, ICALP 2014, to appear. PDF of proceedings version, rev. e5d5661

Thore Husfeldt
  • 780
  • 6
  • 11