Given a directed acyclic graph G=(V,A) and a set A′ of A. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of G can be solved in polynomial time. The question is will the problem remain polynomial if we add the constraint that each path should contain at least one edge of A′?

Do you know any results in the literature that may help in finding the complexity of the problem?