We have the following decision problem. Let $G=(V,E)$ be a directed graph with edge weights $w:E \to \mathbb{R}_{+}$ and $B \in \mathbb{R}$. Is there a set $K$ consisting of directed vertex-disjoint simple paths (in $G$ ofcourse) such that $w(K) \geq B$? Here $w(K) = \sum_{e \in K} w(e)$. Show that this problem is NP-complete.
I have already shown that it is in NP, but I am having some difficulties showing that it is NP-hard. To be specific, I don't know which NP-complete problem I should use for my reduction. My initial thought was Hamiltonian paths but I didn't know how to use this. Can anyone give a hint?
Indeed you can use the Hamiltonian path problem.
Let $G$ be some directed graph with $n$ vertices. We construct a weighted graph $G'$ such that $G$ has a Hamiltonian path if and only if $G'$ admits a path decomposition $K$ with $w(K) \geq B$, with $B = n - 1$.
In fact we have nothing to construct. The graph $G'$ can be the same as $G$, but set a weight of $1$ to every edge. Now, which path decompositions yield $w(K) \geq B$ ? Which ones don't ?