Analyzing Degree Distributions in a Sub-Linear Time Approximation Algorithm for Minimum Vertex Cover Size

Abstract

An algorithm proposed by [Ona+12] for estimating the size of a minimum vertex cover outputs a \((2,\epsilon n)\)-estimate in sub-linear time complexity with respect to the size of the graph, all with high constant probability. Denoting the true size of the minimum vertex cover for a graph \(G\) as \(\text{VC}_{\text{OPT}}(G)\), the number of vertices in \(G\) as \(n\), and some given additive approximation parameter \(\epsilon\in[0,1)\), a \((2,\epsilon n)\)-estimate is defined as any approximation \(X\) that satisfies \(\text{VC}_{\text{OPT}}(G)\leq X\leq 2\cdot\text{VC}_{\text{OPT}}(G)+\epsilon n\). The algorithm may query the degree of any vertex \(v\) of its choice, and the algorithm may ask for the \(i\)-th neighbor of \(v\) for each \(i\in[1,\text{deg}(v)]\).

Research on approximations for vertex cover size has shown the impact that subtleties in degree distributions can have on the efficiency of the algorithms. This paper analyzes graphs with various degree distributions and how they can be manipulated to yield better computational complexities in the approximation algorithm of [Ona+12] without sacrificing accuracy. Furthermore, the paper analyzes various models of random graph generation, and how this approximation algorithm performs when given graphs constructed from these stochastic processes.