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?

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

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<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.

  • $\begingroup$ 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. $\endgroup$ – Farah Mind Sep 14 '19 at 12:43
  • $\begingroup$ I don't know. Maybe. It requires further thinking. And your problem is not only the problem of searching vertex disjoint path. $\endgroup$ – xskxzr Sep 14 '19 at 12:52
  • $\begingroup$ yes, each path should also pass by at least one of the edges of $D'$ $\endgroup$ – Farah Mind Sep 14 '19 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.