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?
