An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio 32 on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S1S1 such that |S1|≤32|S∗|+ξ where S∗S∗ is an optimal cover and ξξ is an error bound identified.