4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cross posted (cs.stackexchange.com/questions/27727/k-path-cover-for-a-dag). $\endgroup$ – R B Jun 15 '14 at 8:21
  • $\begingroup$ 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? $\endgroup$ – Saeed Jun 15 '14 at 14:46
  • $\begingroup$ 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. $\endgroup$ – user25296 Jun 15 '14 at 17:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Saeed Jun 17 '14 at 9:32

Your Answer

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

Browse other questions tagged or ask your own question.