Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-101 | 26th July 2011 19:42

Testing Conductance in General Graphs


Authors: Angsheng Li, Yicheng Pan, Pan Peng
Publication: 26th July 2011 22:43
Downloads: 4306


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

ISSN 1433-8092 | Imprint