Combinatorics, Probability and Computing

Paper

Testing Expansion in Bounded-Degree Graphs

ARTUR CZUMAJa1 and CHRISTIAN SOHLERa2

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: christian.sohler@tu-dortmund.de)

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 UV 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})$.

(Received May 29 2009)

(Revised March 19 2010)

(Online publication June 09 2010)

Footnotes

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).