All About Programming: What is a good algorithm for getting the minimum vertex cover of a tree?

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:

For each u vertex define S+(u) is cover size with vertex u and S-(u) cover without vertex u.
S+(u)= 1 + Sum(S-(v)) for each child v of u.
S-(u)=Sum(max{S-(v),S+(v)}) for each child v of u.
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.

Labels