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 [ minS : |S| = δ |V| frac|partialV(S)| min |S|, |Sc| ] where partialV(S) is the vertex boundary of a set S. 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 Strong Unique Games problem. We give a randomized algorithm running in time n^sf poly(1/δ), which outputs a set S of size Theta(δ n), having vertex expansion at most [ maxleft(O(√φ^* log d log (1/δ)) , tildeO(dlog2(1/δ)) · φ^* right), ] 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 tildeO(1/δ)√φ^* log d and tildeO(1/δ)φ^* √log n due to Louis-Makarychev [TOC'16]. Our algorithm uses the basic SDP relaxation of the problem augmented with rm poly(1/δ) rounds of the Lasserre/SoS hierarchy. Our rounding algorithm is a combination of the rounding algorithms of Raghavendra-Tan [SODA'12] and Austrin-Benabbas-Georgiou [SODA'13]. A key component of our analysis is novel Gaussian rounding lemma for hyperedges which might be of independent interest.