# Vertex disjoint simple paths of length k

A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths.

Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there exist $p$ vertex disjoint simple paths of length $k$ in the graph?

Finding a single simple k-path is known to be single exponent $FPT$ for a long time, what about this variant (with respect to both $p,k$ as parameters)?

It appears that this problem (or a generalization of it) was considered with the Divide and Color approach yielding a $O^*(4^{(k-1)\cdot p})$ run-time algorithm for deciding the problem.
• I don't understand your comment. Using their $graph-packing$ algorithm, you can search for $p$ vertex disjoint copies of the graph $H=P_k$ in time $O^*(4^{(k-1)\cdot p})$. If both $p$ and $k$ are parameters, this is a valid FPT algorithm (which is allowed to run in $O(f(p,k)\cdot poly(n))$. What do you mean by "they will fall in different categories"? – R B Mar 6 '14 at 23:05
• Indeed, every path has to be of length $k$, not just a collection of $p$ disjoint paths with total length $k$. I still don't see the problem. – R B Mar 6 '14 at 23:18