|
TR-789-07
Testing Expansion in Bounded Degree Graphs |
|
| Authors: | Kale, Satyen, Seshadhri, C. |
| Date: | July 2007 |
| Pages: | 7 |
| Download Formats: | [PDF] |
We 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 a graph with expansion $Omega(alpha2)$. The algorithm runs in time $tilde{O}(frac{n^{0.5 + mu}d2}{epsilonalpha2})$ for any given constant $mu > 0$. |
|