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
            )

Answer 2

T(V,E) is a tree, which implies that for any leaf, any minimal vertex cover has to include either the leaf or the vertex adjacent to the leaf. This gives us the following algorithm to finding S, the vertex cover:

1. Find all leaves of the tree (BFS or DFS), O(|V|) in a tree.
2. If (u,v) is an edge such that v is a leaf, add u to the vertex cover, and prune (u,v). This will leave you with a forest T_1(V_1,E_1),...,T_n(U_n,V_n).
3. Now, if V_i={v}, meaning |V_i|=1, then that tree can be dropped since all edges incident on v are covered. This means that we have a termination condition for a recursion, where we have either one or no vertices, and we can compute S_i as the cover for each T_i, and define S as all the vertices from step 2 union the cover of each T_i.

Now, all that remains is to verify that if the original tree has only one vertex, we return 1 and never start the recursion, and the minimal vertex cover can be computed.

Edit:

Actually, after thinking about it for a bit, it can be accomplished with a simple DFS variant.

Answer 3

I hope here you can find more related answer to your question.

---

I was thinking about my solution, probably you will need to polish it but as long as dynamic programing is in one of your tags you probably need to:

1. For each u vertex define S+(u) is cover size with vertex u and S-(u) cover without vertex u.
2. S+(u)= 1 + Sum(S-(v)) for each child v of u.
3. S-(u)=Sum(max{S-(v),S+(v)}) for each child v of u.
4. Answer is max(S+(r), S-(r)) where r is root of your tree.

---

After reading this. Changed the above algorithm to find maximum independent set, since in wiki article stated

A set is independent if and only if its complement is a vertex cover.

So by changing min to max we can find the maximum independent set and by compliment the minimum vertex cover, since both problem are equivalent.

Answer 4

{- Haskell implementation of Artem's algorithm -}

data Tree = Branch [Tree]
    deriving Show

{- first int is the min cover; second int is the min cover that includes the root -}
minVC :: Tree -> (Int, Int)
minVC (Branch subtrees) = let
    costs = map minVC subtrees
    minWithRoot = 1 + sum (map fst costs) in
    (min minWithRoot (sum (map snd costs)), minWithRoot)