Show that Knapsack-like problem on directed graph is NP-hard

Question

Let $G=(V,A)$ represent a directed acyclic graph, where a value $v_i \ge 0$ is assigned to every vertex $u_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum_{i=1}^{N}v_i x_i$

subject to: $\sum_{i=1}^{N} x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

and $x_i(x_j-1) = 0 \quad \forall a\in A: u_i \to u_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u_i$ is chosen, any reachable vertices $u_j$ must also be chosen. Therefore, $x_i(x_j-1) = 0$ for a given arc $u_i \to u_j$ represents that if $u_i$ is chosen ($x_i = 1$) then $u_j$ must be chosen as well ($x_j = 1$).

I want to prove that this is a NP-hard problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum_{i=1}^{M}v_i x_i$

subject to: $\sum_{i=1}^{M} w_i x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an instance of the original problem. Assume an instance of the original problem, with the following properties of $G$:

• $v_i = 0$ for every vertex $u_i$ with incoming arcs.
• All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

• There are $M$ items, where $M$ is the number of vertices $u_i \in G: v_i > 0$.
• The value $v_i$ of each item the value $v_i$ of vertex $u_i$.
• The weight $w_i$ of each item is $1+$ the number of reachable vertices from $u_i$.

Explanation:

• Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
• As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

Questions

1. Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
2. Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an instance of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
3. Assuming that question (2) stands, is my reduction correct?
4. Alternatively, could I demonstrate my case via another reduction?

Answer 1

$x_i \leq x_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x_i=1$ it would push $x_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.