algorithmtreeindependent-set

algorithm to find max independent set in a tree

I need an algorithm to find max independent set in a tree. I'm thinking start from all leaf nodes, and then delete the direct parent nodes to these leaf nodes, then choose the parent nodes of the parent nodes we deleted, repeat this procedure recursively until we get to root. and is this done in O(n) time? any reply is appreciated. thanks.

And could anyone please point me an algorithm to find the max dominating set in a tree.

Solution

  • MAXIMUM INDEPENDENT SET

    You can compute the maximum independent set by a depth first search through the tree.

    The search will compute two values for each subtree in the graph:

    1. A(i) = The size of the maximum independent set in the subtree rooted at i with the constraint that node i must be included in the set.
    2. B(i) = The size of the maximum independent set in the subtree rooted at i with the restriction that node i must NOT be included in the set.

    These can be computed recursively by considering two cases:

    1. The root of the subtree is not included.

      B(i) = sum(max(A(j),B(j)) for j in children(i))

    2. The root of the subtree is included.

      A(i) = 1 + sum(B(j) for j in children(i))

    The size of the maximum independent set in the whole tree is max(A(root),B(root)).

    MAXIMAL DOMINATING SET

    According to the definition of dominating set in wikipedia the maximum dominating set is always trivially equal to including every node in the graph - but this is probably not what you mean?