Couverture de chemin minimum dans un graphique acyclique dirigé

Question

Étant donné un graphique acyclique orienté pondéré $ G = (v, d, w) $ et un ensemble d'arcs $ D '$ de $ D $, où les poids de $ W $ sont sur les sommets. Le problème est de partitionner $ G $ en un nombre minimum de chemins de vertex-disjoint qui couvrent tous les sommets de $ G $ sous réserve des contraintes qui:

1. Le poids de chaque chemin est au plus $ k $.
2. Chaque chemin doit inclure au moins un bord de $ D '$.

Quelle est la complexité de ce problème?