<p>We just answered this for $k=2$: </p>

<p>Andreas Björklund and Thore Husfeldt, <i>Shortest two disjoint paths in polynomial time</i>, ICALP 2014, to appear.
<a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf">PDF of proceedings version, rev. e5d5661</a></p>

CC BY-SA 3.0
2014-04-30T08:34:17.500Z
2014-04-30T08:34:17.500Z
Thore Husfeldt
<p><a href="https://cstheory.stackexchange.com/questions/21973/for-which-values-of-k-is-the-k-disjoint-paths-problem-in-mathcalp">In a related question</a>, 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}$.</p>

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

<p>Related results:</p>

<ul>
<li><p>Using a similar reduction to the one <a href="https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809">I proposed here</a>, it is possible to show that if there's a single source (and $k$ targets), the problem is in $P$.</p></li>
<li><p>There's a <a href="http://ac.els-cdn.com/S0166218X97001212/1-s2.0-S0166218X97001212-main.pdf?_tid=11728ab4-be80-11e3-9e7c-00000aacb361&amp;acdnat=1396894481_d7c17dcda37aaade0c9ed6c63e7c7bc7" rel="nofollow noreferrer">known algorithm</a>(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$ .</p></li>
<li><p>In the same paper, they state that (notice it's not the same problem):</p>

<blockquote>
  <p>"the complexity for fixed $k \geq 3$ remains an open  problem. "</p>
</blockquote></li>
</ul>

<p>What can we say about the "short-$k$-disjoint-paths" problem?</p>

<cc.complexity-theory><ds.algorithms><graph-algorithms><shortest-path><disjoint-paths>
For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?
R B
# For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

(Asked by: username_0 on 2014-04-07)

[In a related question](https://cstheory.stackexchange.com/questions/21973/for-which-values-of-k-is-the-k-disjoint-paths-problem-in-mathcalp), 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](https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809), 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](http://ac.els-cdn.com/S0166218X97001212/1-s2.0-S0166218X97001212-main.pdf?_tid=11728ab4-be80-11e3-9e7c-00000aacb361&acdnat=1396894481_d7c17dcda37aaade0c9ed6c63e7c7bc7)(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?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, shortest-path, disjoint-paths


---

## 1 answers

### Answer by username_1 on 2014-04-30. Score: 8 | Accepted answer

We just answered this for $k=2$:

Andreas Björklund and username_1, *Shortest two disjoint paths in polynomial time*, ICALP 2014, to appear.
[PDF of proceedings version, rev. e5d5661](http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf)


---

