Optimization Problem on a Directed Graph

Question

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.

Answer 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 was last active in 2016, perhaps clarification is not to be had.

Answer 2

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.