New Approximation Bounds for Small-Set Vertex Expansion

Suprovat Ghoshal, Anand Louis

The vertex expansion of the graph is a fundamental graph parameter. Given a graph $G=(V,E)$ and a parameter $\delta \in (0,1/2]$, its $\delta$-Small-Set Vertex Expansion (SSVE) is defined as…