New Approximation Bounds for Small-Set Vertex Expansion

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

The SSVE problem, in addition to being of independent interest as a natural graph partitioning problem, is also of interest due to its connections to the STRONGUNIQUEGAMES problem [GL21]. We give a randomized algorithm running in time n poly(1/δ) , which outputs a set S of size Θ(δn), having vertex expansion at most

where d is the largest vertex degree of the graph, and φ * is the optimal δ-SSVE. The previous best known guarantees for this were the bi-criteria bounds of Õ(1/δ) φ * log d and Õ(1/δ)φ * log n due to .

Our algorithm uses the basic SDP relaxation of the problem augmented with poly(1/δ) rounds of the Lasserre/SoS hierarchy. Our rounding algorithm is a combination of rounding algorithms of [RT12, ABG16]. A key component of our analysis is novel Gaussian rounding lemma for hyperedges which might be of independent interest.