# Maximum independent nodes subset algorithm with strong constraint

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

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.

• 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. – FabioL Sep 12 '15 at 14:39