ECCC-Report TR07-076https://eccc.weizmann.ac.il/report/2007/076Comments and Revisions published for TR07-076en-usThu, 29 Nov 2007 00:00:00 +0200
Revision 1
| Testing Expansion in Bounded Degree Graphs |
Satyen Kale,
Satyen Kale,
C. Seshadhri
https://eccc.weizmann.ac.il/report/2007/076#revision1We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model~\cite{GR}. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and rejects it with high probability if it is $\epsilon$-far from a graph with expansion $\alpha'$ with degree bound $d$, where $\alpha' < \alpha$ is a function of $\alpha$. For edge expansion, we obtain $\alpha' = \Omega(\frac{\alpha^2}{d})$, and for vertex expansion, we obtain $\alpha' = \Omega(\frac{\alpha^2}{d^2})$. In either case, the algorithm
runs in time $\tilde{O}(\frac{n^{(1+\mu)/2}d^2}{\epsilon\alpha^2})$ for any given constant $\mu > 0$.
Thu, 29 Nov 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/076#revision1
Paper TR07-076
| Testing Expansion in Bounded Degree Graphs |
Satyen Kale,
C. Seshadhri
https://eccc.weizmann.ac.il/report/2007/076We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and rejects it with high probability if it is $\epsilon$-far from any graph (with degree bound $2d$) with expansion $\Omega(\alpha^2)$. The algorithm runs in time $\tilde{O}(\frac{n^{0.5 + \mu}d^2}{\epsilon\alpha^2})$ for any given constant $\mu > 0$.
Fri, 10 Aug 2007 17:00:28 +0300https://eccc.weizmann.ac.il/report/2007/076