# For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

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?

We just answered this for $k=2$: