Publications Details

AN expansion tester for bounded degree graphs

Kale, Satyen; Seshadhri, C.

We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, Technical report TR00-020, ECCC, Potsdam, Germany, 2000]. We give a property tester that takes as input a graph with degree bound d, an expansion bound α, and a parameter ε > 0. The tester accepts the graph with high probability if its expansion is more than a, 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 α' = Ω(α2/d ), and for vertex expansion, we obtain α' = Ω(α2/d2 ). In either case, the algorithm runs in time Õ(n (1+μ)/2d2/εα2) for any fixed μ > 0. © 2011 Society for Industrial and Applied Mathematics.