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.

$\endgroup$
  • $\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. Jul 9 '15 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 Jul 9 '15 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. Jul 9 '15 at 18:21
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?

$\endgroup$
  • $\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 Jul 9 '15 at 18:06
  • 1
    $\begingroup$ I'm sorry, you'll have to try harder. $\endgroup$ – Yuval Filmus Jul 9 '15 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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