The Complexity of Approximating Vertex Expansion

We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as φV def = minSCV n . |N(S)|/(|S| |V\ S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(&root;φVlog d) where d is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than C(&root;φVlog d) for an absolute constant C. In particular, this implies for all constant "≥ &epsil; > 0, it is SSE-hard to distinguish whether the vertex expansion ≤ ý or at least an absolute constant. The analogous threshold for edge expansion is &root; φ with no dependence on the degree (Here φ denotes the optimal edge expansion). Thus our results suggest that vertex expansion is harder to approximate than edge expansion. In particular, while Cheeger's algorithm can certify constant edge expansion, it is SSE-hard to certify constant vertex expansion in graphs.