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.

  • $\begingroup$ 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"? $\endgroup$
    – R B
    Mar 6 '14 at 23:05
  • $\begingroup$ 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. $\endgroup$
    – R B
    Mar 6 '14 at 23:18
  • $\begingroup$ Yes you are right I made a mistake, In your problem you don't have specific set of source and terminals, so this is correct. $\endgroup$
    – Saeed
    Mar 6 '14 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.