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.That said, $2$-$\text{DPP}$ admits a nearly linear algorithm for general undirected graphs.Is there anything known for any higher value of $k$ (assuming fixed $k$ value)? What about $k=3$?
For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?
ds.algorithms;graph algorithms;np hardness;complexity classes;disjoint paths
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 case and recently bounded genus case, running time improved.For directed graph it's NP-Complete even case of 2-disjoint path problem. But in planar graphs is FPT by result of Marx et al., in graphs of bounded genus is at least in XP (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of Slivkins, 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).