<p>It appears that this problem (or a generalization of it) was considered with the <a href="http://download.springer.com/static/pdf/205/chp%253A10.1007%252F11917496_6.pdf?auth66=1394304624_4356f85023e9c4dd6d0926ee3f9365f8&amp;ext=.pdf" rel="nofollow">Divide and Color</a> approach yielding a $O^*(4^{(k-1)\cdot p})$ run-time algorithm for deciding the problem. </p>

CC BY-SA 3.0
2014-03-06T23:05:02.713Z
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
CC BY-SA 3.0
2014-03-06T23:18:02.477Z
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
CC BY-SA 3.0
2014-03-06T23:25:59.583Z
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.
Saeed
CC BY-SA 3.0
2014-03-06T18:55:31.287Z
2014-03-06T23:27:10.400Z
2014-03-06T23:27:10.400Z
R B
<p>A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths.</p>

<p>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?</p>

<p>Finding a single simple k-path is <a href="http://www.tau.ac.il/~nogaa/PDFS/col5.pdf" rel="nofollow">known to be</a> single exponent $FPT$ for a long time, what about this variant (with respect to both $p,k$ as parameters)?</p>

<ds.algorithms><parameterized-complexity><fixed-parameter-tractable>
Vertex disjoint simple paths of length k
R B
# Vertex disjoint simple paths of length k

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

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](http://www.tau.ac.il/~nogaa/PDFS/col5.pdf) single exponent $FPT$ for a long time, what about this variant (with respect to both $p,k$ as parameters)?

**Tags:** ds.algorithms, parameterized-complexity, fixed-parameter-tractable


---

## 1 answers

### Answer by username_0 on 2014-03-06. Score: 1 | Accepted answer

It appears that this problem (or a generalization of it) was considered with the [Divide and Color](http://download.springer.com/static/pdf/205/chp%253A10.1007%252F11917496_6.pdf?auth66=1394304624_4356f85023e9c4dd6d0926ee3f9365f8&ext=.pdf) approach yielding a $O^\*(4^{(k-1)\cdot p})$ run-time algorithm for deciding the problem.

> **Comments:**
> **username_0**: 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"?  
> **username_0**: 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.  
> **username_1**: 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.  

---

