We consider the problem of estimating the size, VC(G), of a minimum
vertex cover of a graph G, in sublinear time,
by querying the incidence relation of the graph. We say that
an algorithm is an (\alpha,\eps)-approximation algorithm
if it outputs with high probability an estimate \widehat{VC}
such that VC(G) - \eps n \leq \widehat{VC} \leq \alpha\cdot VC(G) + \eps n,
where n is the number of vertices of G.

We show that the query complexity of such algorithms must grow at
least linearly with the average degree \bd of the graph. In particular
this means that for dense graphs it is not possible to design
an algorithm whose complexity is o(n).

On the positive side we first describe a
simple (O(\log(\bd/\eps),\eps)-approximation algorithm,
whose query complexity is \eps^{-2}\cdot (\bd/\eps)^{\log(\bd/\eps)+O(1)}.

We then show a reduction from local distributed approximation algorithms
to sublinear approximation algorithms.
Using this reduction and the distributed algorithm of
Kuhn, Moscibroda, and Wattenhofer~\cite{KMW}
we can get an (O(1),\eps)-approximation algorithm,
whose query complexity is
\eps^{-2}\cdot (\bd/\eps)^{O(\log(\bd/\eps)}.

We consider the problem of estimating the size, VC(G), of a
minimum vertex cover of a graph G, in sublinear time,
by querying the incidence relation of the graph. We say that
an algorithm is an (\alpha,\eps)-approximation algorithm
if it outputs with high probability an estimate \widehat{VC}
such that
VC(G) - \eps n \leq \widehat{VC} \leq \alpha\cdot VC(G) + \eps n,
where n is the number of vertices of G.

We show that the query complexity of such algorithms must grow at
least linearly with the average degree \bd of the graph.
In particular this means that for dense graphs it is not possible
to design an algorithm whose complexity is o(n).

On the positive side we first describe a
simple (O(\log(\bd/\eps),\eps)-approximation algorithm,
whose query complexity is
\eps^{-2}\cdot (\bd/\eps)^{\log(\bd/\eps)+O(1)}.

We then show a reduction from local distributed approximation
algorithms to sublinear approximation algorithms.
Using this reduction and the distributed algorithm of
Kuhn, Moscibroda, and Wattenhofer~\cite{KMW}
we can get an (O(1),\eps)-approximation algorithm,
whose query complexity is
\eps^{-2}\cdot (\bd/\eps)^{O(\log(\bd/\eps)}.