×

# Minimum Vertex Cover

 2 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? asked 23 Sep '16, 20:16 187●2●13 accept rate: 0%

 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. answered 24 Sep '16, 00:01 4★linkret 236●5 accept rate: 25% thanks for pointing that out. (24 Sep '16, 00:13)
 0 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/ answered 24 Sep '16, 00:41 4★thedark 84●2 accept rate: 9%
 0 @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. answered 06 Dec, 18:54 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,106
×2

question asked: 23 Sep '16, 20:16

question was seen: 1,475 times

last updated: 06 Dec, 18:54