<p>For undirected graph problem admits a FPT algorithm for any fixed $k$. Robertson and Seymour, Graph Minor XIII. Their algorithm runs in time $2^{2^{2^{2^{O(k)}}}} P(n)$ which means for $k = O(\log\log\log\log n)$ is polynomial. But it's not known whether there is better bound for $k$ or not. In special cases like undirected <a href="http://arxiv.org/abs/1310.2378" rel="nofollow">planar</a> case and recently <a href="http://arxiv.org/abs/1309.7820" rel="nofollow">bounded genus</a> case, running time improved.</p>

<p>For directed graph it's NP-Complete even case of <a href="http://www.sciencedirect.com/science/article/pii/0304397580900092" rel="nofollow">2-disjoint path</a> problem. But in planar graphs is FPT by result of <a href="http://arxiv.org/abs/1304.4207" rel="nofollow">Marx et al.</a>, in graphs of bounded genus is <a href="http://homepages.cwi.nl/~lex/files/dppg.pdf" rel="nofollow">at least in XP</a> (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of <a href="http://link.springer.com/chapter/10.1007/978-3-540-39658-1_44" rel="nofollow">Slivkins</a>, for tournaments is NP-complete (not known if is FPT or even XP, edge disjoint version admits XP algorithm by result of Seymour et al).</p>

CC BY-SA 4.0
2022-10-13T21:52:57.017Z
Do you know if it's still the case (six years later) that there's no algorithm with better dependence on k for this problem?
Naysh
CC BY-SA 4.0
2022-10-14T10:33:44.727Z
@Naysh, there are some work with Kawarabayashi and Wollan on this. It could be that they have better dependence on k, not sure. You may search the related literature based on their work.
Saeed
CC BY-SA 3.0
2014-04-06T13:35:55.417Z
2014-04-09T11:47:38.530Z
2014-04-09T11:47:38.530Z
Saeed
<p>Here's what I know.</p>

<ol>
<li><p>For undirected graphs, the problem admits a 'nonconstructive' FPT algorithm based on Robertson-Seymour theory. The running time is $f(k) n^3$ where $f$ is a fast-growing function.</p></li>
<li><p>For directed graphs, the problem is $\sf{NP}$-complete for any constant $k \geq 3$. In the case of planar directed graphs, it is polynomial for fixed $k$: there is a relatively simple $n^{O(k)}$ algorithm due to Schrijver ('Finding k Disjoint Paths in a Directed Planar Graph', SICOMP) and a more involved FPT algorithm with running time $f(k) poly(n)$ due to Cygan et al., where $f(k)$ is a double-exponential function ('The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable', FOCS 2013).</p></li>
</ol>

<p>Also, if I remember right there are some cases where the edge-disjoint version is easier, but I couldn't recollect the details.</p>

CC BY-SA 3.0
2014-04-06T12:13:40.967Z
2014-04-06T12:13:40.967Z
Super8
<p>The <span class="math-container">$k$</span>-Vertex-Disjoint Paths Problem (<span class="math-container">$k$</span>-<span class="math-container">$\text{DPP}$</span>) is defined as follows:</p>
<blockquote>
<p>Input: A graph <span class="math-container">$G=(V,E)$</span> and <span class="math-container">$k$</span> pairs of vertices <span class="math-container">$(s_1,t_1),\ldots,(s_k,t_k)$</span>.</p>
<p>Question: Does there exist <span class="math-container">$k$</span>-pairwise vertex-disjoint paths <span class="math-container">$P_1,\ldots,P_k$</span>, such that <span class="math-container">$P_i$</span> goes from <span class="math-container">$s_i$</span> to <span class="math-container">$t_i$</span>?</p>
</blockquote>
<p>The problem, for general <span class="math-container">$k$</span>, is <a href="http://link.springer.com/article/10.1007/BF01202792#page-1" rel="nofollow noreferrer">known to be NP-complete even for planar graphs of max degree 3</a>.</p>
<p>That said, <span class="math-container">$2$</span>-<span class="math-container">$\text{DPP}$</span> <a href="http://www.informatik.uni-augsburg.de/thi/personen/tholey_files/crntholey06.pdf" rel="nofollow noreferrer">admits a nearly linear algorithm</a> for general undirected graphs.</p>
<p>Is there anything known for any higher value of <span class="math-container">$k$</span> (assuming fixed <span class="math-container">$k$</span> value)? What about <span class="math-container">$k=3$</span>?</p>

CC BY-SA 3.0
2014-04-06T12:09:20.720Z
According to this anwser 
http://cstheory.stackexchange.com/questions/21926/problems-that-are-hard-to-prove-in-mathcalp/21950#21950, 
the problem is in P for all fixed $k$. Isn't it?
User Mahfud
<ds.algorithms><graph-algorithms><np-hardness><complexity-classes><disjoint-paths>
For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?
R B
# For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

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

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows:

> Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s\_1,t\_1),\ldots,(s\_k,t\_k)$.
>
> Question: Does there exist $k$-pairwise vertex-disjoint paths $P\_1,\ldots,P\_k$, such that $P\_i$ goes from $s\_i$ to $t\_i$?

The problem, for general $k$, is [known to be NP-complete even for planar graphs of max degree 3](http://link.springer.com/article/10.1007/BF01202792#page-1).

That said, $2$-$\text{DPP}$ [admits a nearly linear algorithm](http://www.informatik.uni-augsburg.de/thi/personen/tholey_files/crntholey06.pdf) for general undirected graphs.

Is there anything known for any higher value of $k$ (assuming fixed $k$ value)? What about $k=3$?

**Tags:** ds.algorithms, graph-algorithms, np-hardness, complexity-classes, disjoint-paths

> **Comments:**
> **username_1**: According to this anwser  http://cstheory.stackexchange.com/questions/21926/problems-that-are-hard-to-prove-in-mathcalp/21950#21950,  the problem is in P for all fixed $k$. Isn't it?  

---

## 2 answers

### Answer by username_2 on 2014-04-06. Score: 7 | Accepted answer

For undirected graph problem admits a FPT algorithm for any fixed $k$. Robertson and Seymour, Graph Minor XIII. Their algorithm runs in time $2^{2^{2^{2^{O(k)}}}} P(n)$ which means for $k = O(\log\log\log\log n)$ is polynomial. But it's not known whether there is better bound for $k$ or not. In special cases like undirected [planar](http://arxiv.org/abs/1310.2378) case and recently [bounded genus](http://arxiv.org/abs/1309.7820) case, running time improved.

For directed graph it's NP-Complete even case of [2-disjoint path](http://www.sciencedirect.com/science/article/pii/0304397580900092) problem. But in planar graphs is FPT by result of [Marx et al.](http://arxiv.org/abs/1304.4207), in graphs of bounded genus is [at least in XP](http://homepages.cwi.nl/~lex/files/dppg.pdf) (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of [Slivkins](http://link.springer.com/chapter/10.1007/978-3-540-39658-1_44), for tournaments is NP-complete (not known if is FPT or even XP, edge disjoint version admits XP algorithm by result of Seymour et al).

> **Comments:**
> **username_3**: Do you know if it's still the case (six years later) that there's no algorithm with better dependence on k for this problem?  
> **username_2**: @username_3, there are some work with Kawarabayashi and Wollan on this. It could be that they have better dependence on k, not sure. You may search the related literature based on their work.  

---

### Answer by username_4 on 2014-04-06. Score: 5

Here's what I know.

1. For undirected graphs, the problem admits a 'nonconstructive' FPT algorithm based on Robertson-Seymour theory. The running time is $f(k) n^3$ where $f$ is a fast-growing function.
2. For directed graphs, the problem is $\sf{NP}$-complete for any constant $k \geq 3$. In the case of planar directed graphs, it is polynomial for fixed $k$: there is a relatively simple $n^{O(k)}$ algorithm due to Schrijver ('Finding k Disjoint Paths in a Directed Planar Graph', SICOMP) and a more involved FPT algorithm with running time $f(k) poly(n)$ due to Cygan et al., where $f(k)$ is a double-exponential function ('The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable', FOCS 2013).

Also, if I remember right there are some cases where the edge-disjoint version is easier, but I couldn't recollect the details.


---

