Abstract:
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)}$.

Abstract:
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)}$.