# 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

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$.