What is a good algorithm for getting the minimum vertex cover of a tree?

Question

What is a good algorithm for getting the minimum vertex cover of a tree?

INPUT:

The node's neighbours.

OUTPUT:

The minimum number of vertices.

Answer 1

I didn't fully understand after reading the answers here, so I thought I'd post one from here

The general idea is that you root the tree at an arbitrary node, and ask whether that root is in the cover or not. If it is, then you calculate the min vertex cover of the subtrees rooted at its children by recursing. If it isn't, then every child of the root must be in the vertex cover so that every edge between the root and its children is covered. In this case, you recurse on the root's grandchildren.

So for example, if you had the following tree:

    A
   / \
  B   C
 / \ / \
D  E F  G

Note that by inspection, you know the min vertex cover is {B, C}. We will find this min cover.

Here we start with A.

A is in the cover

We move down to the two subtrees of B and C, and recurse on this algorithm. We can't simply state that B and C are not in the cover, because even if AB and AC are covered, we can't say anything about whether we will need B and C to be in the cover or not.

(Think about the following tree, where both the root and one of its children are in the min cover ({A, D})

  A
 /|\___
B C    D
      /|\
     E F G

)

A is not in the cover

But we know that AB and AC must be covered, so we have to add B and C to the cover. Since B and C are in the cover, we can recurse on their children instead of recursing on B and C (even if we did, it wouldn't give us any more information).

"Formally"

Let C(x) be the size of the min cover rooted at x.

Then,

C(x) = min ( 
            1 + sum ( C(i) for i in x's children ),                    // root in cover
            len(x's children) + sum( C(i) for i in x's grandchildren)  // root not in cover
            )