1
$\begingroup$

I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation:

Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to the cover, and remove all edges incident to $v$ or $w$.

Please give me insights on how to pick an example.

Improve this question
$\endgroup$
3
  • $\begingroup$ What have you tried? What approaches have you considered? Note that you can't prove something is a 2-approximation by finding an example; all you can do with an example is prove that its approximation ratio is $\ge 2$. If that's what you are trying to do, what is the best example you have come up with? In other words, of all the examples you've tried, which one has the highest approximation ratio of them all? We expect you to make a serious effort to solve your problem on your own before asking here, and to show us in the question what you've tried. $\endgroup$
    – D.W. ♦
    Commented Jul 9, 2015 at 16:55
  • $\begingroup$ Well it does not seem to make sense to list out all of the examples I have tried so far. I have tried bipartite graphs and other graphs that have been proven not ideal if greedy algorithm is used. I keep getting optimal solutions with this algorithm (it picks the vertex with highest degree, and extends from one of its edges) $\endgroup$
    – James the Great
    Commented Jul 9, 2015 at 17:57
  • $\begingroup$ I didn't suggest that you list out all the examples you tried so far, so I'm not sure why you bring that up. I suggested you list the one best example you've found, out of all the ones you've tried so far (the one example that had the highest approximation ratio of all). Have you found any example at all where the approximation ratio is strictly greater than one? I suggest you edit the question to include this information, including the classes of graphs you've considered, and the best example you've found so far. $\endgroup$
    – D.W. ♦
    Commented Jul 9, 2015 at 18:21

1 Answer 1

Reset to default
1
$\begingroup$

Hint:

  1. Prove the stronger claim that if $M$ is any matching, then any vertex cover must contain at least $|M|$ vertices.

  2. Conversely, if $M$ is any maximal matching (a matching which cannot be extended), then the $2|M|$ vertices in $M$ form a vertex cover.

  3. Show that the greedy algorithm that you describe constructs a maximal matching.

  4. Conclude that your algorithm (modified so that it outputs a set of vertices rather than a set of edges) is a 2-approximation for minimum vertex cover.

  5. Consider the complete bipartite graph $K_{n,n}$. What is its minimum vertex cover? What vertex cover does your algorithm produce?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for my ignorance, but I don't understand the first 4 hints. I tried the 5th hint, with n = 3, and the min vertex cover seems to be 2 (with one vertex on each side). My algorithm produces 3 (if I am correct), so is this 2-approximation? $\endgroup$
    – James the Great
    Commented Jul 9, 2015 at 18:06
  • 1
    $\begingroup$ I'm sorry, you'll have to try harder. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2015 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.