ECCC-Report TR05-094https://eccc.weizmann.ac.il/report/2005/094Comments and Revisions published for TR05-094en-usSun, 28 Aug 2005 00:00:00 +0300
Revision 1
| On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms Revision of: TR05-094 |
Michal Parnas,
Dana Ron
https://eccc.weizmann.ac.il/report/2005/094#revision1
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)}$.
Sun, 28 Aug 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/094#revision1
Paper TR05-094
| On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms |
Michal Parnas,
Dana Ron
https://eccc.weizmann.ac.il/report/2005/094We 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)}$.
Thu, 25 Aug 2005 23:16:08 +0300https://eccc.weizmann.ac.il/report/2005/094