An expansion tester for bounded degree graphs
S Kale, C Seshadhri - International Colloquium on Automata, Languages …, 2008 - Springer
International Colloquium on Automata, Languages, and Programming, 2008•Springer
We consider the problem of testing graph expansion (either vertex or edge) in the bounded
degree model 10. We give a property tester that given a graph with degree bound d, an
expansion bound α, and a parameter ε> 0, accepts the graph with high probability if its
expansion is more than α, and rejects it with high probability if it is ε-far from any graph with
expansion α′ with degree bound d, where α′< α is a function of α. For edge expansion,
we obtain α'=Ω(α^2d), and for vertex expansion, we obtain α'=Ω(α^2d^2). In either case, the …
degree model 10. We give a property tester that given a graph with degree bound d, an
expansion bound α, and a parameter ε> 0, accepts the graph with high probability if its
expansion is more than α, and rejects it with high probability if it is ε-far from any graph with
expansion α′ with degree bound d, where α′< α is a function of α. For edge expansion,
we obtain α'=Ω(α^2d), and for vertex expansion, we obtain α'=Ω(α^2d^2). In either case, the …
Abstract
We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [10]. We give a property tester that given a graph with degree bound d, an expansion bound α, and a parameter ε> 0, accepts the graph with high probability if its expansion is more than α, and rejects it with high probability if it is ε-far from any graph with expansion α′ with degree bound d, where α′ < α is a function of α. For edge expansion, we obtain , and for vertex expansion, we obtain . In either case, the algorithm runs in time for any given constant μ> 0.
Springer