# 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:

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

What is the complexity of this problem?

• Why do you tag hamiltonian-path? – xskxzr Sep 11 at 15:00
• because the minimum path cover problem is a generalization of the hamiltonian path – Farah Mind Sep 11 at 15:10

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. 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.
• if $k$ is a constant, the problem becomes polynomial? because searching a minimum number of vertex disjoint paths that cover an acyclic graph can be solved in polynomial time by transforming it in a matching problem. – Farah Mind Sep 14 at 12:43
• yes, each path should also pass by at least one of the edges of $D'$ – Farah Mind Sep 14 at 12:59