Problem Detail: 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
Asked By : Fabio Lipreri
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47101 Ask a Question Download Related Notes/Documents
