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?


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.