-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – sukunrt Dec 6 '13 at 22:25
  • $\begingroup$ 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? $\endgroup$ – Bar Dec 7 '13 at 11:55
0
$\begingroup$

Hint: If you are counting the number of MIS that include the root.

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?

If suppose the the subtrees rooted at the grand children of the root have k1,k2,k3,k4...,kt Maximum independent sets.(k1 for the 1st grand child and so on) Now if you select one MIS from the k1 available for the first grand child, one from the k2 available for the second and so on,and add the root to it you get a MIS of the whole tree.

So you have k1 choices in the first one, k2 in the second one, k3 in the third. So shouldn't the total number of MIS be the product of these? k1*k2*k3*...*kt

BTW you need to make sure that there is one MIS that contains the root

$\endgroup$
  • $\begingroup$ That's where I'm stuck. I don't see a way to calculate the number of MIS's just by looking at the n. o. MIS's of the grandchildren or children of the root. For example a tree with only 2 nodes connected to one another has a NMIS of 2 (max MIS size is 1, we can choose either node as the MIS) while a tree with just a root and 2 children has a NMIS of 1 (max MIS size is 2, only one way to choose). Where is the mathematical relationship there? $\endgroup$ – Bar Dec 7 '13 at 17:08
  • $\begingroup$ The k1*k2*..*kt formula does not hold. Imagine a tree, one root, two children, one grandchild. The NMIS for the grandchild is 1. For the parent of the grandchild it's 2. FOr the other child it's one. For the root of the tree the NMIS is 3, as the size of the MIS is 2 and there are three possible way to select 2 non-adjacent vertices from such a tree. This also works if you simply have a chain of 4 vertices(which is the same tree as above, but rooted at a leaf), each one connected to the next. The grandchild here will have an NMIS of 2, while the root will have 3. $\endgroup$ – Bar Dec 8 '13 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.