Minimum Vertex Cover

general
,
1

Hi, i was solving this problem, i think i am implementing a greedy algorithm, getting WA for this solution. The solution is self explanatory, i did a dfs on the tree to calculate level of each node and then printed the minimum of total number of node of same parity(odd/even), am i right doing this?

1 Like
2

This greedy solution is wrong. For example, imagine you have vertex 1 connected with vertex 2, and vertex 1 connected with 100 other vertices and vertex 2 connected with 100 other vertices. Obviously the correct answer is 2: we only include vertex 1 and 2, but your solution would print 101. Try to think of another greedy, or a dp.

2 Likes
3

thanks for pointing that out.

4

The problem with the greedy method has already been explained.Lets build a dynamic programming paradigm for it. Let,

  1. dp[i][1] = answer of the problem rooted at node i if node i is put in set.

  2. dp[i][0] = answer of the problem rooted at node i if node i is not put in set.

If we put a vertex in the set then we don’t need to select any of its children, as we have covered all edges from this node to its children

If we don’t select the vertex then we need to definitely put all its children in the set as we want to cover all edges from this node to its children

dp[i][1] = 1 + (for every child v of i -> sum(min(dp[v][0] , dp[v][1]))

dp[i][0] = for every child v of i -> sum(dp[v][1])

now we need minimum of dp[1][0] and dp[1][1]

here is implementation for better understanding http://paste.ubuntu.com/23221571/

1 Like
5

@thedark, Your solution is correct but your interpretation is not.

“If we put a vertex in the set then we don’t need to select any of its children, as we have covered all edges from this node to its children”

This is false. If we put a vertex in the set then we may or may not want to include some of its children.

As you can see, you wrote dp[i][1] = 1+(sum(min(dp[v][0], dp[v][1])). Reflect on it.