Minimum Path cover in a Directed Acyclic Graph Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-disjoint paths that cover all the vertices of $G$ subject to the constraints that:


the weight of each path is at most $k$.
each path should include at least one edge of $D'$.


What is the complexity of this problem?
This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard.

Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i&lt;j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there exist 2 vertex-disjoint paths satisfying your conditions if and only if the weights can be partitioned into two subsets both with sum $k$, which is exactly the partition problem. Hence, your problem is NP-hard.