# Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around.

I've been trying to use a similar technique (ie. recursing through the childred and then the grandchildren of a node) to find the number of such sets but I have not been able to work it out.

Any help?

• For a particular node in the tree, if you include it in the maximum independent set,can you include it's children, grand children? If you don't include it, what can you do? – sukunrt Dec 6 '13 at 22:25
• Well if you include the node you can include its grandchildren to the maximum set, but not its children. That's the way you count the size of the MIS by adding one when visiting each grandchild, and then take the max of the two sums (max{Sum(children),Sum(grandchildren) + 1}). Is there someway to use a similar technique that will calculate the number of MIS's? – Bar Dec 7 '13 at 11:55

As you said a MIS that includes the root cannot include its children and you will recurse on the grand children. So if for the ith grandchild it has k_i Maximum independent sets(k_i is the number of MIS for the subtree rooted at the grandchild i). Can you obtain a formula for the number of MIS for tree rooted at root?