The Complexity of Approximating Vertex Expansion

Anand Louis, Prasad Raghavendra, Santosh Vempala

We study the complexity of approximating the vertex expansion of graphs $G=(V,E)$, defined as \[ Φ^V := \min_{S \subset V} n \cdot \frac{|N(S)|}{|S| |V \backslash S|}. \] We give…