Theory of Computing
-------------------
Title     : Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
Authors   : Anand Louis and Yury Makarychev
Volume    : 12
Number    : 17
Pages     : 1-25
URL       : https://theoryofcomputing.org/articles/v012a017

Abstract
--------

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 
$O~(\delta^{-1}\sqrt{\log n})$-approximation. The second algorithm 
finds a set with expansion 
$O~(\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 $O~(\delta^{-1} \sqrt{\log n})$-approximation
algorithm and an algorithm that finds a set with vertex expansion
$O~(\delta^{-1}\sqrt{\phi^V \log d_{\max}} + \delta^{-1}\phi^V)$ 
(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).