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

作者：Vignatti Andre L^*; da Silva Murilo V G

来源：Theoretical Computer Science, 2016, 647: 101-111.

DOI：10.1016/j.tcs.2016.08.002

• Chung-Lu random graph model
• Britton random graph model
• Generalized random graph model
• Approximation algorithms
• Vertex cover problem
• Power-law graphs

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(-beta), where beta > 2 and c is a normalizing constant, the expected approximation ratio is 1 + zeta(beta)Li--1(beta)(e(-rho(beta))), where zeta(beta) is the Riemann Zeta function of beta, Li(beta) is the polylogarithmic special function of beta and rho(beta) = Li beta-2(1/e)/zeta(beta-1).

• 出版日期2016-9-27