Approximability of the vertex cover problem in power-law graphs
In this paper we construct an approximation algorithm for the Minimum Vertex Cover (Min-VC) problem with an expected approximation ratio of 2 ? ? ( ? ) ? 1 ? 1 2 ? 2 ? ? ( ? ? 1 ) ? ( ? ) for random power-law graphs  in the P(?,?) P ( ? , ? ) model due to Aiello et al. Here ?(?) ? ( ? ) is the Riemann zeta function of ?. We obtain this result by combining the Nemhauser and Trotter approach for Min-VC with a new deterministic rounding procedure which achieves an approximation ratio of 3 2 on a subset of low degree vertices for which the expected contribution to the cost of the associated linear program is sufficiently large.
vertex cover problem power-law graphs approximation algorithms