Minimum vertex cover in generalized random graphs with power law degree distribution

• Published in: Theoretical computer science 2016-09, Vol.647, p.101-111
• Main Authors: Vignatti, André L., da Silva, Murilo V.G.
• Format: Article
• Language: English
• Subjects: Approximation; Approximation algorithms; Britton random graph model; Chung–Lu random graph model; Computer simulation; Constants; Generalized random graph model; Graphs; Mathematical analysis; Mathematical models; Power law; Power-law graphs; Vertex cover problem
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2016.08.002

In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ci−β, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)−1Liβ(e−ρ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and ρ(β)=Liβ−2(1e)ζ(β−1).