<p><strong>lemma 1.</strong> <em>The posted problem (as I understand it) is NP-hard, even on DAGs</em>, </p>

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

<p>Let the <span class="math-container">$x_i$</span>'s be <span class="math-container">$b$</span>-bit integers for some <span class="math-container">$b$</span>, so the input instance has size polynomial in <span class="math-container">$n$</span> and <span class="math-container">$b$</span> and each <span class="math-container">$x_i$</span> is an integer in <span class="math-container">$\{1,2,\ldots, 2^b\}$</span>.</p>

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

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

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

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

<p>Given that <a href="https://cstheory.stackexchange.com/users/35895/graphman">Graphman</a> was last active in 2016, perhaps clarification is not to be had.</p>

CC BY-SA 4.0
2019-10-16T00:41:00.533Z
2019-10-16T00:41:00.533Z
Neal Young
<p>I haven't thought of a solution, but here's a way of factoring the problem.</p>

<p>I assume <span class="math-container">$G$</span> is finite. Every directed graph can be factored into a DAG of strongly connected components (SCCs) by (IIRC) Tarjan's algorithm.</p>

<p>Pick a vertex <span class="math-container">$v$</span> in some root SCC <span class="math-container">$C$</span> (i.e. <span class="math-container">$C$</span> has in-degree 0 in the DAG of SCCs) where <span class="math-container">$|C| \geq 2$</span>. If <span class="math-container">$v$</span> is activated some in-neighbor must also be activated. But it too must have an activated in-neighbor, etc., and this regress is either infinite, contradicting my assumption that <span class="math-container">$G$</span> is finite, or form a cycle, which as far as I understand is ruled out.</p>

<p>So any such <span class="math-container">$C$</span> can be eliminated: no vertex in it can be activated.</p>

<p>A non-root SCC <span class="math-container">$D$</span> can inductively be eliminated if all the SCCs <span class="math-container">$C_1, \ldots, C_k$</span> with edges to <span class="math-container">$D$</span> have been thus eliminated: it is a root in the reduced graph.</p>

<p>Maybe it's then possible to solve the remaining SCCs one by one, and combining their solutions using dynamic programming on the DAG of SCCs.</p>

<p>Then again, I'm not sure I fully understand the problem.  Given a 3SAT instance, consider the following graph:</p>

<p>Have three vertices per variable, <span class="math-container">$y_i$</span>, <span class="math-container">$t_i$</span>, <span class="math-container">$f_i$</span>, each having activation requirement <span class="math-container">$0$</span>, with edges <span class="math-container">$(y_i, t_i)$</span> and <span class="math-container">$(y_i, f_i)$</span>.</p>

<p>For each clause, have a vertex <span class="math-container">$c_j$</span> with in-edges from <span class="math-container">$t_i$</span> for every variable <span class="math-container">$x_i$</span> occurring positively in clause <span class="math-container">$j$</span> and from <span class="math-container">$f_i$</span> for every variable occurring negatively in the clause. Each clause vertex has activation requirement 1.</p>

<p>Have one vertex <span class="math-container">$\varphi$</span> for the formula value, with in-edges from every clause and with activation requirement equal to the number of clauses.</p>

<p>This is almost complete: given a 3SAT instance, add a clause <span class="math-container">$(x_i \lor \lnot x_i)$</span> for every variable, then perform the above reduction.</p>

<p>This requires either <span class="math-container">$t_i$</span> or <span class="math-container">$f_i$</span> to be satisfied (uh, activated) for every variable <span class="math-container">$x_i$</span>. If the 3SAT instance is satisfiable then some such activation plus a choice of edges into clauses and into the formula gives an edge-minimal way of meeting all activation requirements. If it is not satisfiable, some variable has to be both true and false to satisfy the activation requirements.</p>

<p>3SAT can not be solved in polynomial time (with e.g. dynamic programming) unless P = NP, so I don't quite follow what the dynamic programming solution is. But maybe that's because I misunderstood the problem.</p>

<p>Maybe you can add a loop from <span class="math-container">$\varphi$</span> to each <span class="math-container">$y_i$</span> to make this construction strongly connected, and give each <span class="math-container">$y_i$</span> an incoming activation requirement of 1.</p>

<p>Like I said, I don't quite understand the problem but I hope some of these ideas are helpful.</p>

CC BY-SA 4.0
2019-10-15T11:57:33.317Z
2019-10-15T11:57:33.317Z
Jonas Kölker
<p>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:</p>

<p>$$\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}$$</p>

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

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

<p>Any pointers are appreciated. Thanks a lot.</p>

CC BY-SA 3.0
2015-10-10T00:43:58.283Z
1. Do you mean for your objective function to be $\sum_i \sum_{j \in P(i)} x_{ij}$?  Or is $i$ a fixed value, and you want to minimize $\sum_{j \in P(i)} x_{ij}$ for that fixed value of $i$?  Also, for your "such that", do you intend to require that equation to hold for all $i$, or only for a single fixed value of $i$?  2. What are the inputs, and what are the free variables?  Are the $v_i$'s provided as input, and the $a_i$'s and $x_{ij}$'s can be chosen freely to maximize the objective function?  Can you edit the question accordingly?
D.W.
CC BY-SA 3.0
2015-10-10T00:46:25.090Z
3. I noticed that you seem to have two different accounts: http://cstheory.stackexchange.com/users/35896/graphman and http://cstheory.stackexchange.com/users/35895/graphman. Having multiple accounts is usually discouraged, as it can easily lead to violation of site rules regarding sock puppets (in fact, editing your own post is technically probably such an instance, as it gives you +2 reputation you wouldn't have gotten otherwise, though maybe no one will care about that specific thing). Anyway, I encourage you to merge your accounts. See http://cstheory.stackexchange.com/help/merging-accounts
D.W.
CC BY-SA 3.0
2015-10-10T07:11:08.797Z
Fixed those issues. Thanks for your feedback!
GraphMan
CC BY-SA 3.0
2015-10-10T09:06:08.960Z
I'm trying to figure out what's going on with the activation here. Your first equality says each vertex's activation equals the sum of the activations of its adjacent predecessors, and thus all activations along a walk are monotonically increasing. If you have a directed cycle, this implies that all activations of vertices in the cycle are equal. What happens to the activations, then, if you add an extra chord to the cycle somewhere, making the activation of one of its vertices twice that of each of its predecessors in the cycle?
Yonatan N
CC BY-SA 3.0
2015-10-10T18:24:23.763Z
I don't think a directed cycle can exist in the solution, as it by definition will monotonically increase activations of nodes on that cycle without bound. To have all equal activations along a walk is also not possible since at least one predecessor node is selected for each node in the cycle. So whatever the optimal set of edges selected the resulting graph has to be acyclic. But this does also require an additional assumption to ensure feasibility for each node: there has to be a feasible activation set (set of predecessor nodes) that does not result in a cycle. We can assume that.
GraphMan
CC BY-SA 3.0
2015-10-10T21:23:18.843Z
I have to make a correction to the above comment. It is possible to have the  same activations along a walk if exactly one predecessor node is selected for every node along that path. But if these nodes were part of a cycle, we would still have the issue that the activations along that cycle will be unbounded.
GraphMan
<ds.algorithms><graph-algorithms><optimization>
Optimization Problem on a Directed Graph
GraphMan
# Optimization Problem on a Directed Graph

(Asked by: username_0 on 2015-10-09)

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.

**Tags:** ds.algorithms, graph-algorithms, optimization
> **Comments:**
> **username_1**: 1. Do you mean for your objective function to be $\sum_i \sum_{j \in P(i)} x_{ij}$?  Or is $i$ a fixed value, and you want to minimize $\sum_{j \in P(i)} x_{ij}$ for that fixed value of $i$?  Also, for your "such that", do you intend to require that equation to hold for all $i$, or only for a single fixed value of $i$?  2. What are the inputs, and what are the free variables?  Are the $v_i$'s provided as input, and the $a_i$'s and $x_{ij}$'s can be chosen freely to maximize the objective function?  Can you edit the question accordingly?  
> **username_1**: 3. I noticed that you seem to have two different accounts: http://cstheory.stackexchange.com/users/35896/graphman and http://cstheory.stackexchange.com/users/35895/graphman. Having multiple accounts is usually discouraged, as it can easily lead to violation of site rules regarding sock puppets (in fact, editing your own post is technically probably such an instance, as it gives you +2 reputation you wouldn't have gotten otherwise, though maybe no one will care about that specific thing). Anyway, I encourage you to merge your accounts. See http://cstheory.stackexchange.com/help/merging-accounts  
> **username_0**: Fixed those issues. Thanks for your feedback!  
> **username_2**: I'm trying to figure out what's going on with the activation here. Your first equality says each vertex's activation equals the sum of the activations of its adjacent predecessors, and thus all activations along a walk are monotonically increasing. If you have a directed cycle, this implies that all activations of vertices in the cycle are equal. What happens to the activations, then, if you add an extra chord to the cycle somewhere, making the activation of one of its vertices twice that of each of its predecessors in the cycle?  
> **username_0**: I don't think a directed cycle can exist in the solution, as it by definition will monotonically increase activations of nodes on that cycle without bound. To have all equal activations along a walk is also not possible since at least one predecessor node is selected for each node in the cycle. So whatever the optimal set of edges selected the resulting graph has to be acyclic. But this does also require an additional assumption to ensure feasibility for each node: there has to be a feasible activation set (set of predecessor nodes) that does not result in a cycle. We can assume that.  
> **username_0**: I have to make a correction to the above comment. It is possible to have the  same activations along a walk if exactly one predecessor node is selected for every node along that path. But if these nodes were part of a cycle, we would still have the issue that the activations along that cycle will be unbounded.  

---

## 2 answers

### Answer by username_3 on 2019-10-16. Score: 1

**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](https://cstheory.stackexchange.com/users/35895/graphman) was last active in 2016, perhaps clarification is not to be had.


---

### Answer by username_4 on 2019-10-15. Score: -1

I haven't thought of a solution, but here's a way of factoring the problem.

I assume $G$ is finite. Every directed graph can be factored into a DAG of strongly connected components (SCCs) by (IIRC) Tarjan's algorithm.

Pick a vertex $v$ in some root SCC $C$ (i.e. $C$ has in-degree 0 in the DAG of SCCs) where $|C| \geq 2$. If $v$ is activated some in-neighbor must also be activated. But it too must have an activated in-neighbor, etc., and this regress is either infinite, contradicting my assumption that $G$ is finite, or form a cycle, which as far as I understand is ruled out.

So any such $C$ can be eliminated: no vertex in it can be activated.

A non-root SCC $D$ can inductively be eliminated if all the SCCs $C\_1, \ldots, C\_k$ with edges to $D$ have been thus eliminated: it is a root in the reduced graph.

Maybe it's then possible to solve the remaining SCCs one by one, and combining their solutions using dynamic programming on the DAG of SCCs.

Then again, I'm not sure I fully understand the problem. Given a 3SAT instance, consider the following graph:

Have three vertices per variable, $y\_i$, $t\_i$, $f\_i$, each having activation requirement $0$, with edges $(y\_i, t\_i)$ and $(y\_i, f\_i)$.

For each clause, have a vertex $c\_j$ with in-edges from $t\_i$ for every variable $x\_i$ occurring positively in clause $j$ and from $f\_i$ for every variable occurring negatively in the clause. Each clause vertex has activation requirement 1.

Have one vertex $\varphi$ for the formula value, with in-edges from every clause and with activation requirement equal to the number of clauses.

This is almost complete: given a 3SAT instance, add a clause $(x\_i \lor \lnot x\_i)$ for every variable, then perform the above reduction.

This requires either $t\_i$ or $f\_i$ to be satisfied (uh, activated) for every variable $x\_i$. If the 3SAT instance is satisfiable then some such activation plus a choice of edges into clauses and into the formula gives an edge-minimal way of meeting all activation requirements. If it is not satisfiable, some variable has to be both true and false to satisfy the activation requirements.

3SAT can not be solved in polynomial time (with e.g. dynamic programming) unless P = NP, so I don't quite follow what the dynamic programming solution is. But maybe that's because I misunderstood the problem.

Maybe you can add a loop from $\varphi$ to each $y\_i$ to make this construction strongly connected, and give each $y\_i$ an incoming activation requirement of 1.

Like I said, I don't quite understand the problem but I hope some of these ideas are helpful.


---

