Testing Expansion in Bounded-Degree Graphs

Source abstract

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 $\widetilde{\O}(\sqrt{n})$ . We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every α-expander with probability at least $\frac23$ and rejects every graph that is ϵ-far from any α*-expander with probability at least $\frac23$ , where $\expand^* \,{=}\, \Theta(\frac{\expand^2}{d^2 \log(n/\epsilon)})$ 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 $\O(\frac{d^2 \sqrt{n} \log(n/\epsilon)} {\expand^2 \epsilon^3})$ .