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$ Commented 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$ Commented 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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.