Revision #1 Authors: Michal Parnas, Dana Ron

Accepted on: 28th August 2005 00:00

Downloads: 3010

Keywords:

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

TR05-094 Authors: Michal Parnas, Dana Ron

Publication: 25th August 2005 23:16

Downloads: 3390

Keywords:

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