We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately O(n^{1/2}).
We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an a*-expander with probability at least 2/3, where a* = O(a^2/(d^2 log(n/epsilon))), d is the maximum degree of the graphs, and a graph is called epsilon-far from an a*-expander if one has to modify (add or delete) at least epsilon d n of its edges to obtain an a*-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^2 n^{1/2} log(n/epsilon)/(a^2 epsilon^3)). We will also briefly discuss the recent improvements due to Kale and Seshadhri, Nachmias and Shapira, who reduced the dependency in the expansion of the rejected graphs from O(a^2/(d^2 log(n/epsilon))) to O(a^2/d^2).
Related Links
* http://dx.doi.org/10.1109/FOCS.2007.4389526 - FOCS 2007 paper
view more