2
$\begingroup$

I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints:

  • The selected nodes must be the optimal solution (maximal sum of weight).
  • If one node is flagged no adjacent nodes can be flagged.
  • If a node is flagged it will be called: "directly controlled", the adjacent nodes instead will be called: "indirectly controlled", all nodes must be directly or indirectly controlled.

I think is a dynamic programming problem (a greedy approach didn't find always a optimal solution), the first two constraints are a typical maximum independent subset problems, but i cannot find a solution with the third constraint included. Any idea? Thanks

$\endgroup$
1
$\begingroup$

A set satisfying condition (3) is known as a dominating set. The exercise asks for a maximum weight dominating independent set.

If all node weights are positive, then every optimal solution is automatically a dominating set (why?), regardless of whether the graph is a tree or not. In the more general case in which negative weights are allowed, you can use a standard dynamic programming approach. Root the tree at an arbitrary node, and for every subtree rooted at some internal node $v$, compute the maximum weight independent set in the following three cases:

  • The independent set is dominating and includes $v$.
  • The independent set is dominating and doesn't include $v$.
  • The independent set is dominating if $v$ is removed (it is allowed to dominate $v$ as well), and doesn't include $v$.

I'll let you complete the details.

$\endgroup$
  • $\begingroup$ Thanks for your help. My tree have all positive weights, i've tried the independent set algorithm with some particular tree and, as you said, is always a dominating set, so intuitively i've understood that it's true, now i'm trying to find a better formal demonstration. $\endgroup$ – FabioL Sep 12 '15 at 14:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.