pdf icon
Volume 12 (2016) Article 17 pp. 1-25
APPROX-RANDOM 2014 Special Issue
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
Received: March 31, 2015
Revised: September 20, 2016
Published: October 30, 2016
Download article from ToC site:
[PDF (301K)]    [PS (1613K)]    [PS.GZ (364K)]
[Source ZIP]
Keywords: approximation algorithms, hypergraph expansion, small-set expansion
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25

Abstract: [Plain Text Version]

$ \newcommand{\wto}{\tilde{O}} $

The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the hyperedges cut to the size of the smaller side of the cut. We study the Hypergraph Small-Set Expansion problem, which, for a parameter $\delta \in (0,1/2]$, asks to compute the cut having the least expansion while having at most $\delta$ fraction of the vertices on the smaller side of the cut. We present two algorithms. Our first algorithm gives an $\wto(\delta^{-1} \sqrt{\log n})$-approximation. The second algorithm finds a set with expansion $\wto(\delta^{-1}(\sqrt{d_{\max}r^{-1}\log r\, \phi^*} + \phi^*))$ in an $r$-uniform hypergraph with maximum degree $d_{\max}$ (where $\phi^*$ is the expansion of the optimal solution). Using these results, we also obtain algorithms for the Small-Set Vertex Expansion problem: we get an $\wto(\delta^{-1} \sqrt{\log n})$-approximation algorithm and an algorithm that finds a set with vertex expansion \[ \wto\left(\delta^{-1}\sqrt{\phi^V \log d_{\max} } + \delta^{-1} \phi^V\right) \] (where $\phi^V$ is the vertex expansion of the optimal solution).

For $\delta=1/2$, Hypergraph Small-Set Expansion is equivalent to the hypergraph expansion problem. In this case, our approximation factor of $O(\sqrt{\log n})$ for expansion in hypergraphs matches the corresponding approximation factor for expansion in graphs due to Arora, Rao, and Vazirani (JACM 2009).

A conference version of this paper appeared in the Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2014).