Minimum Vertex Cover in Generalized Random Graphs with Power Law Degree Distribution

Abstract

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 , where and c is a normalizing constant, the expected approximation ratio is , where is the Riemann Zeta function of ß, is the polylogarithmic special function of ß and .

Publication
Theoretical Computer Science, Vol. 647, p. 101-111
André Vignatti
André Vignatti
Associate Professor