1
$\begingroup$

I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise disjoint). I need to find the smallest set of paths such that at least one node of each set is covered. If the size of each V_i was 1, I know the problem is polynomial (it can be converted into a max-matching problem in a bipartite graph). But the argument does not work for this case. Do you know if this variant is known? I am mostly interested in knowing whether it is still in P or it becomes NP-Complete. Thanks!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.