Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-094 | 28th August 2005 00:00

On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms Revision of: TR05-094

RSS-Feed




Revision #1
Authors: Michal Parnas, Dana Ron
Accepted on: 28th August 2005 00:00
Downloads: 1220
Keywords: 


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


Paper:

TR05-094 | 9th August 2005 00:00

On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms





TR05-094
Authors: Michal Parnas, Dana Ron
Publication: 25th August 2005 23:16
Downloads: 1053
Keywords: 


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



ISSN 1433-8092 | Imprint