TR11-101 Authors: Angsheng Li, Yicheng Pan, Pan Peng

Publication: 26th July 2011 22:43

Downloads: 3622

Keywords:

In this paper, we study the problem of testing the conductance of a

given graph in the general graph model. Given distance parameter

$\varepsilon$ and any constant $\sigma>0$, there exists a tester

whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log

n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where

$n$ is the number of vertices and $m$ is the number of edges of the

input graph. With probability at least $2/3$, the tester accepts all

graphs of conductance at least $\Phi$, and rejects any graph that is

$\varepsilon$-far from any graph of conductance at least $\alpha'$

for $\alpha'=\Omega(\Phi^2)$. This result matches the best testing

algorithm for the bounded degree graph model in \cite{KS07}.

Our main technical contribution is the \emph{non-uniform Zig-Zag

product}, which generalizes the standard Zig-Zag product given by

Reingold et. al. \cite{RVW02} to the unregular case. It converts any

graph to a regular one and keeps (roughly) the size and conductance,

by choosing a proper Zig-Zag graph sequence. This makes it easy to

test the conductance of the given graph on the new one. The analysis

and applications of non-uniform Zig-Zag product may be independently

interesting.