# Variant of an approximation algorithm for vertex cover

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?

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