Optimization Problem on a Directed Graph I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For each node we can compute the "activation value" $a_i$ as a sum of the activation values of the selected predecessor nodes, i.e.:
$$a_i = \sum_{j \in P(i)}x_{ji}a_{j}$$
where $x_{ij} \in \{0,1\}$ are edge selector variables and $P(i)$ is the set of predecessor nodes of $i$. The optimization objective is for each node in the graph to select a set of incoming edges with minimal cost that "activate" that node:

$$\underset{x}{\text{argmin  }}\sum_{i} \sum_{j \in P(i)} a_ix_{ji}$$
$$\text{  such that  }  \sum_{j \in P(i)}x_{ji}a_{j}\ge v_i, \forall{i}$$

We can assume that there exist some leaf nodes in the graph whose activation value is 1, and that each node in the graph can be activated for a large enough subset of incoming edges.

If $G$ is a DAG, then we can solve this with dynamic programming, but I can't seem to figure out if there is a way to do this on a general DG, or if its NP hard.

Any pointers are appreciated. Thanks a lot.
lemma 1. The posted problem (as I understand it) is NP-hard, even on DAGs, 

Proof. The proof is by reduction from Subset Sum.  Given a Subset Sum instance with $n$ positive integers $x_1, x_2, \ldots, x_n$ and target $T$, the reduction produces the following instance of your problem.  The instance will have a minimal solution (one with objective equal to the sum of the activation values -- the minimum possible) if and only if some subset of the $x_i$'s sums to $T$.

Let the $x_i$'s be $b$-bit integers for some $b$, so the input instance has size polynomial in $n$ and $b$ and each $x_i$ is an integer in $\{1,2,\ldots, 2^b\}$.

Construct a "tower" gadget with two leaves $u_0, w_0$ with activation 1.  For each $i\in\{1,2,\ldots, b\}$, add two vertices $u_i, w_i$ each with activation threshold $2^i$ and two incoming edges: $(u_{i-1}, u_i)$, $(u_{i-1}, w_{i})$, $(w_{i-1}, u_i)$, $(w_{i-1}, w_i)$.  In any feasible solution to the instance (so far), each such vertex $u_i$ and $w_i$ will have to use both its incoming edges, and will have incoming activation value exactly equal to its activation threshold $2^i$.

Next, for each integer $x_i$ in the given Subset Sum instance, construct a vertex $X_i$ with activation threshold $x_i$, with edges from every $u_j$.  In any minimal solution, each $X_i$ will use just those incoming edges that represent the binary representation of $x_i$, thereby achieving incoming activation value equal to $x_i$ (and this is always possible).

Finally, construct a "root" vertex $R$ with activation value $T$ (the Subset Sum target) and edges from every vertex $X_i$.  There will be a subset of edges into $R$ to use to achieve activation value $T$ if and only if there is a subset of the $x_i$'s that sums to $T$.  $~~~\Box$

What am I missing?  As I understand the problem, showing NP-hardness seems like a nice homework exercise...  

Given that Graphman was last active in 2016, perhaps clarification is not to be had.