<p>I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the <strong>minimum</strong> k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with length at most k such that every vertex  must belong at least to a path (can belong to more than one). The minimum k-path cover problem asks for the minimum size of a k-path cover. </p>

CC BY-SA 3.0
2014-06-15T08:21:17.297Z
Cross posted (http://cs.stackexchange.com/questions/27727/k-path-cover-for-a-dag).
R B
CC BY-SA 3.0
2014-06-15T14:46:01.783Z
Isn't this trivial? Take every single vertex as a path, the result is what you want. Do you mean the number of paths should be at most $k$ not length of each of them? or minimum set size?
Saeed
CC BY-SA 3.0
2014-06-15T17:54:11.460Z
Sorry, I did not make myself clear. What I really want to know is if there is any polynomial time algorithm that find in a DAG the minimum number of k-paths needed to cover all the vertices. Assuming, also, that a vertex can belong to more than one k-path.
user25296
CC BY-SA 3.0
2014-06-17T09:32:38.030Z
To me seems the problem is NPC, rough idea is using [those](http://arxiv.org/abs/1312.1526) gadget construction for disjoint path problem in planar DAGs, they are in such a way that all paths together are covering the graph, you can set $k$ to be some small number say 20, then ask whether there is a path cover of size at most $k\cdot t$ for some $t\in O(n)$. To model it in a way that forces use of disjoint path structure needs some work though.
Saeed
<graph-algorithms><directed-acyclic-graph><covering-problems>
K-path cover problem for a DAG
user25296
# K-path cover problem for a DAG

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

I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the **minimum** k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with length at most k such that every vertex must belong at least to a path (can belong to more than one). The minimum k-path cover problem asks for the minimum size of a k-path cover.

**Tags:** graph-algorithms, directed-acyclic-graph, covering-problems
> **Comments:**
> **username_1**: Cross posted (http://cs.stackexchange.com/questions/27727/k-path-cover-for-a-dag).  
> **username_2**: Isn't this trivial? Take every single vertex as a path, the result is what you want. Do you mean the number of paths should be at most $k$ not length of each of them? or minimum set size?  
> **username_0**: Sorry, I did not make myself clear. What I really want to know is if there is any polynomial time algorithm that find in a DAG the minimum number of k-paths needed to cover all the vertices. Assuming, also, that a vertex can belong to more than one k-path.  
> **username_2**: To me seems the problem is NPC, rough idea is using [those](http://arxiv.org/abs/1312.1526) gadget construction for disjoint path problem in planar DAGs, they are in such a way that all paths together are covering the graph, you can set $k$ to be some small number say 20, then ask whether there is a path cover of size at most $k\cdot t$ for some $t\in O(n)$. To model it in a way that forces use of disjoint path structure needs some work though.  

---

## 0 answers

