You are not logged in. Please login at www.codechef.com to post your questions!

×

Minimum Vertex Cover

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

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%


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.

link

answered 24 Sep '16, 00:01

linkret's gravatar image

4★linkret
2365
accept rate: 25%

thanks for pointing that out.

(24 Sep '16, 00:13) ashwanigautam3★

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/

link

answered 24 Sep '16, 00:41

thedark's gravatar image

4★thedark
842
accept rate: 9%

edited 24 Sep '16, 00:43

@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.

link

answered 06 Dec, 18:54

aparichit_vyav's gravatar image

0★aparichit_vyav
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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