Here is an approximation algorithm that finds vertex cover of a graph.

 C = {}
 E' = {Edge set}
 while E' =/ 0
   Let (u,v) be an arbitrarily edge of E'
    C = C U {u,v}
    remove E' incident on u and v.
return C

A variant: what if instead of removing edges incident on both $u$ and $v$, we removed only $u$. Would this affect the optimal vertex cover? If so, how?

I somehow feel the optimal vertex cover remains the same whereas only the number of steps to remove the edges would increase increasing time and space complexity. Am I right?

  • $\begingroup$ What do you think? Have you tried running your modification on some examples? $\endgroup$ Nov 15, 2018 at 9:09
  • $\begingroup$ Nothing that the algorithm does can affect the optimal vertex cover. Are you interested in the approximation ratio of the algorithm, perchance? $\endgroup$ Nov 15, 2018 at 9:11
  • $\begingroup$ i wanted to check the quality of the algorithm? $\endgroup$ Nov 15, 2018 at 19:35
  • $\begingroup$ This “quality” is known as the approximation ratio. $\endgroup$ Nov 15, 2018 at 20:28
  • $\begingroup$ What is an approximation ratio?And how to calculate? $\endgroup$ Nov 15, 2018 at 20:33

1 Answer 1


Consider a star consisting of a center $x$ connected to the vertices $y_1,\ldots,y_n$. Your modified algorithm could act as follows:

  1. Choose the edge $(x,y_1)$; add $x,y_1$ to the vertex cover; remove all edges incident to $y_1$.
  2. Choose the edge $(x,y_2)$; add $x,y_2$ to the vertex cover; remove all edges incident to $y_2$.
  3. ...

I'll let you take it from here.


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.