Finding the largest subsets of nodes in a tree subject to some constraints?

Question

Given a Tree like the following:

            X
    /               \
    1               6
/   |   \       /   |   \   
2   5   9       1   5   3
   ...             ...

For each node there is a number(except for the root), in the example the numbers are random.

If a node is taken, the next child-node of this node cannot be taken. But the child-child-node is allowed to take. So it's just not okay to take following nodes.

I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken.

I searched for solutions, I found the red-black-tree which is very similar but not really useful.

Any ideas on this?

Answer 1

The problem you're trying to solve is called the maximum independent set problem applied to trees.

As a hint, think about the following:

• For each complete subtree of the tree, think about the optimal solution for that subtree in two cases - the case where you include that node in the solution, and the case where you exclude that node from the solution.

• Use dynamic programming: work from the leaves of the tree up to the root of the tree.

Hope this helps!