The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders. This assumption implies the hardness of several other computational problems, and the optimality of certain known approximation algorithms. The small set expansion hypothesis is related to the unique games conjecture, another unproven computational hardness assumption according to which accurately approximating the value of certain games is computationally infeasible. If the small set expansion hypothesis is true, then so is the unique games conjecture.
Background
The edge expansion of a set X {\displaystyle X} of vertices in a graph G {\displaystyle G} is defined as | ∂ X | | X | , {\displaystyle {\frac {|\partial X|}{|X|}},}
where the vertical bars denote the number of elements of a set, and ∂ X {\displaystyle \partial X} denotes the set of edges that have one endpoint in X {\displaystyle X} and the other endpoint in its complement. This number can be as low as zero, when X {\displaystyle X} is a connected component of the graph, because in this case there are no edges connecting X {\displaystyle X} to other parts of the graph. A graph is called regular or d {\displaystyle d} -regular when every vertex is incident to the same number of edges, d {\displaystyle d} , the degree of the graph. For a d {\displaystyle d} -regular graph, the maximum possible edge expansion is d {\displaystyle d} . This expansion is achieved by any subset X {\displaystyle X} that induces an independent set, as in this case all of the edges that touch vertices in X {\displaystyle X} belong to ∂ X {\displaystyle \partial X} . The edge expansion of a graph with n {\displaystyle n} vertices is defined to be the minimum edge expansion among its subsets of at most n / 2 {\displaystyle n/2} vertices. Instead, the small set expansion is defined as the same minimum, but only over smaller subsets, of at most n / log 2 n {\displaystyle n/\log _{2}n} vertices. Informally, a small set expander is a graph whose small set expansion is large.
Statement The small set expansion hypothesis uses a real number ε {\displaystyle \varepsilon } as a parameter to formalize what it means for the small set expansion of a graph to be large or small. It asserts that, for every ε > 0 {\displaystyle \varepsilon >0} , it is NP-hard to distinguish between d {\displaystyle d} -regular graphs with small set expansion at least ( 1 − ε ) d {\displaystyle (1-\varepsilon )d} (good small set expanders), and d {\displaystyle d} -regular graphs with small set expansion at most ε d {\displaystyle \varepsilon d} (very far from being a small set expander). Here, the degree d {\displaystyle d} is a variable that might depend on the choice of ε {\displaystyle \varepsilon } , unlike in many applications of expander graphs where the degree is assumed to be a fixed constant.
… excerpt ends here. Continue reading the full article.
