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.