ECCC-Report TR11-101https://eccc.weizmann.ac.il/report/2011/101Comments and Revisions published for TR11-101en-usTue, 26 Jul 2011 22:43:50 +0300
Paper TR11-101
| Testing Conductance in General Graphs |
Yicheng Pan,
Angsheng Li,
Pan Peng
https://eccc.weizmann.ac.il/report/2011/101In 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.Tue, 26 Jul 2011 22:43:50 +0300https://eccc.weizmann.ac.il/report/2011/101