New Approximation Bounds for Small-Set Vertex Expansion

• Published in: arXiv.org 2023-11
• Main Authors: Ghoshal, Suprovat, Anand, Louis
• Format: Article
• Language: English
• Subjects: Algorithms; Parameters; Rounding
• ISSN: 2331-8422

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 \[ \min_{S : |S| = \delta |V|} \frac{|{\partial^V(S)}|}{ \min \{ |S|, |S^c| \} } \] where \(\partial^V(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/\delta)}\), which outputs a set \(S\) of size \(\Theta(\delta n)\), having vertex expansion at most \[ \max\left(O(\sqrt{\phi^* \log d \log (1/\delta)}) , \tilde{O}(d\log^2(1/\delta)) \cdot \phi^* \right), \] where \(d\) is the largest vertex degree of the graph, and \(\phi^*\) is the optimal \(\delta\)-SSVE. The previous best-known guarantees for this were the bi-criteria bounds of \(\tilde{O}(1/\delta)\sqrt{\phi^* \log d}\) and \(\tilde{O}(1/\delta)\phi^* \sqrt{\log n}\) due to Louis-Makarychev [TOC'16]. Our algorithm uses the basic SDP relaxation of the problem augmented with \({\rm poly}(1/\delta)\) 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.