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 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 2

{- 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)

Answer 3

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.