# K-path cover problem for a DAG

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.

• Cross posted (cs.stackexchange.com/questions/27727/k-path-cover-for-a-dag). – R B Jun 15 '14 at 8:21
• 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 Jun 15 '14 at 14:46
• 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 Jun 15 '14 at 17:54
• To me seems the problem is NPC, rough idea is using those 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 Jun 17 '14 at 9:32