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$.
  • $\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 '20 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 '20 at 23:16

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.


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.