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,
- For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
- 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.
Unfortunately, the greedy approach you mentioned is not correct. It fails for a test case like this one.
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.
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
