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.

• 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. Oct 10 '15 at 0:43
• 3. I noticed that you seem to have two different accounts: cstheory.stackexchange.com/users/35896/graphman and 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 cstheory.stackexchange.com/help/merging-accounts – D.W. Oct 10 '15 at 0:46
• Fixed those issues. Thanks for your feedback! – GraphMan Oct 10 '15 at 7:11
• 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 Oct 10 '15 at 9:06
• 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 Oct 10 '15 at 18:24

2 Answers

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.

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.