1
$\begingroup$

Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?

Input: $G = (V,E)$

  1. Set $C \gets \emptyset$ and $E' \gets E$.
  2. while $E' \neq \emptyset$ do:
    • Pick any edge $(u,v) \in E'$.
    • $C \gets C \cup \{u\}$.
    • Remove from $E'$ all edges incident to $u$.
  3. return $C$.
Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome! As the question asker, you can upvote and/or accept an answer. If you find it helpful, please upvote. If it is the best answer that solves your problem, accept it. That is the basic protocol. Have you checked what to do when someone answers?. (This comment will be deleted upon feedback) $\endgroup$
    – John L.
    Apr 29, 2020 at 23:24
  • $\begingroup$ You do not have enough reputation to upvote, yet. However, you can accept an answer to your own question. $\endgroup$
    – John L.
    May 15, 2020 at 23:16

1 Answer 1

Reset to default
1
$\begingroup$

No, this is a terrible algorithm. Consider a star graph: the vertices are $x,y_1,\ldots,y_n$, and the edges are $(x,y_1),\ldots,(x,y_n)$. Your algorithm goes over the edges in an arbitrary order, and always picks the $y$ vertices. It ends up with $n$ vertices rather than the optimal $1$ vertex solution.

Improve this answer
$\endgroup$

Your Answer

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

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