Skip to main content
1 of 2

k vertex-disjoint paths cover in DAG

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?