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−12β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 32 on a subset of low degree vertices for which the expected contribution to the cost of the associated linear program is sufficiently large.