1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Oct 10 '15 at 0:43
  • 1
    $\begingroup$ 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 $\endgroup$ – D.W. Oct 10 '15 at 0:46
  • $\begingroup$ Fixed those issues. Thanks for your feedback! $\endgroup$ – GraphMan Oct 10 '15 at 7:11
  • $\begingroup$ 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? $\endgroup$ – Yonatan N Oct 10 '15 at 9:06
  • 1
    $\begingroup$ 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. $\endgroup$ – GraphMan Oct 10 '15 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.