Minimum Vertex Cover on Trees

help
#1

Hello all,

I’m trying to solve SPOJ PT07X - Vertex Cover (https://www.spoj.com/problems/PT07X/). I tried implementing a greedy approach based on the following,

  1. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
  2. For each internal node, if any of its children is not selected, then select this node.

However, I’m getting WA on SPOJ. Here’s my solution for the same. (https://ideone.com/Z3VD2L)
Kindly, let me know where I’m going wrong. Thank you.

#2

Unfortunately, the greedy approach you mentioned is not correct. It fails for a test case like this one.

image
image604×567 28.5 KB

Your algorithm will only select the vertices marked with red pointers which will only cover the edges marked with white lines leaving 2 edges not selected at all. This will make your code’s output to be 3 whereas it is impossible to have a vertex cover of this tree of size 3 and the correct answer should be 4.

Think of some other solution. However, if you have never done dynamic programming on trees, this may be a good time to learn it.

#3

Thank you. I now understand the shortcoming of the greedy method. I will look into DP on trees for solving this problem. Cheers !

1 Like