a1 Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, Coventry CV4 7AL, UK (e-mail: A.Czumaj@warwick.ac.uk)
a2 Department of Computer Science, Technische Universität Dortmund, D-44221 Dortmund, Germany (e-mail: firstname.lastname@example.org)
We consider the problem of testing expansion in bounded-degree graphs. We focus on the notion of vertex expansion: an α-expander is a graph G = (V, E) in which every subset U ⊆ V of at most |V|/2 vertices has a neighbourhood of size at least α ⋅ |U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time . We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every α-expander with probability at least and rejects every graph that is ϵ-far from any α*-expander with probability at least , where and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is .
(Received May 29 2009)
(Revised March 19 2010)
(Online publication June 09 2010)
† Research supported in part by DFG grant Me 872/8-3, by EPSRC grant EP/G064679/1, by EPSRC Science and Innovation Award EP/D063191/1 and the Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick.
‡ A preliminary version of this paper appeared in Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 570–578 (2007).