  We give a nearly optimal sublinear-time algorithm for approximating the size
of a minimum vertex cover in a graph G. The algorithm may query the degree
deg(v) of any vertex v of its choice, and for each 1 <= i <= deg(v), it may ask
for the i-th neighbor of v. Letting VC_opt(G) denote the minimum size of vertex
cover in G, the algorithm outputs, with high constant success probability, an
estimate VC_estimate(G) such that VC_opt(G) <= VC_estimate(G) <= 2 * VC_opt(G)
+ epsilon*n, where epsilon is a given additive approximation parameter. We
refer to such an estimate as a (2,epsilon)-estimate. The query complexity and
running time of the algorithm are ~O(avg_deg * poly(1/epsilon)), where avg_deg
denotes the average vertex degree in the graph. The best previously known
sublinear algorithm, of Yoshida et al. (STOC 2009), has query complexity and
running time O(d^4/epsilon^2), where d is the maximum degree in the graph.
Given the lower bound of Omega(avg_deg) (for constant epsilon) for obtaining
such an estimate (with any constant multiplicative factor) due to Parnas and
Ron (TCS 2007), our result is nearly optimal.
  In the case that the graph is dense, that is, the number of edges is
Theta(n^2), we consider another model, in which the algorithm may ask, for any
pair of vertices u and v, whether there is an edge between u and v. We show how
to adapt the algorithm that uses neighbor queries to this model and obtain an
algorithm that outputs a (2,epsilon)-estimate of the size of a minimum vertex
cover whose query complexity and running time are ~O(n) * poly(1/epsilon).
