algorithm to find max independent set in a tree

Question

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.

Answer 1

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?

Answer 2

Simple and fast approach:

As long as the graph is not empty, iteratively add a leaf v (degree 1) to the independent set V and remove v and its neighbor.

This should work, since

• A tree always has a degree-1-vertex,

• Adding a degree-1-vertex to V preserves optimality and

• The result of such a step again gives a tree or a forest which is a union of trees.