Skip to main content

$k$ vertex-disjoint paths cover in Directed Acyclic Graph

The problem is that: in a directed acyclic graph $G$, I want to know the maximum vertices that can be covered by $k$ vertex-disjoint paths.

Obviously, the value of $k$ is smaller than the minimum path coverage of $G$. Are there any approximation algorithms that can solve this problem?