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$ – Yuval Filmus Nov 15 '18 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$ – Yuval Filmus Nov 15 '18 at 9:11
  • $\begingroup$ i wanted to check the quality of the algorithm? $\endgroup$ – khushboo shah Nov 15 '18 at 19:35
  • $\begingroup$ This “quality” is known as the approximation ratio. $\endgroup$ – Yuval Filmus Nov 15 '18 at 20:28
  • $\begingroup$ What is an approximation ratio?And how to calculate? $\endgroup$ – khushboo shah Nov 15 '18 at 20:33

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, privacy policy and cookie policy

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