Small Set Expansion Hypothesis

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$ of vertices in a graph $G$ is defined as $\frac,$
where the vertical bars denote the number of elements of a set, and $\partial X$ denotes the set of edges that have one endpoint in $X$ and the other endpoint in its complement. This number can be as low as zero, when $X$ is a connected component of the graph, because in this case there are no edges connecting $X$ to other parts of the graph. A graph is called regular or $d$-regular when every vertex is incident to the same number of edges, $d$, the degree of the graph. For a $d$-regular graph, the maximum possible edge expansion is $d$. This expansion is achieved by any subset $X$ that induces an independent set, as in this case all of the edges that touch vertices in $X$ belong to $\partial X$.

The edge expansion of a graph with $n$ vertices is defined to be the minimum edge expansion among its subsets of at most $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$ 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 $\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 $\varepsilon>0$, it is NP-hard to distinguish between graphs with small set expansion at least $(1-\varepsilon)d$ (good small set expanders), and graphs with small set expansion at most $\varepsilon d$ (very far from being a small set expander). Here, the degree $d$ is a variable that might depend on the choice of $\varepsilon$, unlike in many applications of expander graphs where the degree is assumed to be a fixed constant.

Consequences

The small set expansion hypothesis implies the NP-hardness of several other computational problems. Because it is only a hypothesis, this does not prove that these problems actually are NP-hard. Nevertheless, it suggests that it would be difficult to find an efficient solution for these problems, because solving any one of them would also solve other problems whose solution has so far been elusive (including the small set expansion problem itself). In the other direction, this implication opens the door to disproving the small set expansion hypothesis, by providing other problems through which it could be attacked.

In particular, there exists a polynomial-time reduction from the recognition of small set expanders to the problem of determining the approximate value of unique games, showing that the small set expansion hypothesis implies the unique games conjecture. Boaz Barak has suggested more strongly that these two hypotheses are equivalent. In fact, the small set expansion hypothesis is equivalent to a restricted form of the unique games conjecture, asserting the hardness of unique games instances whose underlying graphs are small set expanders. On the other hand, it is possible to quickly solve unique games instances whose graph is "certifiably" a small set expander, in the sense that their expansion can be verified by sum-of-squares optimization.

Another application of the small set expansion hypothesis concerns the computational problem of approximating the treewidth of graphs, a structural parameter closely related to expansion. For graphs of treewidth $w$, the best approximation ratio known for a polynomial time approximation algorithm is $O(\sqrt)$. The small set expansion hypothesis, if true, implies that there does not exist an approximation algorithm for this problem with constant approximation ratio. It also can be used to imply the inapproximability of finding a complete bipartite graph with the maximum number of edges (possibly restricted to having equal numbers of vertices on each side of its bipartition) in a larger graph.

The small set expansion hypothesis implies the optimality of known approximation ratios for certain variants of the edge cover problem, in which one must choose as few vertices as possible to cover a given number of edges in a graph.

History and partial results

The small set expansion hypothesis was formulated, and connected to the unique games conjecture, by Prasad Raghavendra and David Steurer in 2010, as part of a body of work for which they were given the 2018 Michael and Sheila Held Prize of the National Academy of Sciences.

One approach to resolving the small set expansion hypothesis is to seek approximation algorithms for the edge expansion of small vertex sets that would be good enough to distinguish the two classes of graphs in the hypothesis. In this light, the best approximation known, for the edge expansion of subsets of at most $n/\log n$ vertices in a $d$-regular graph, has an approximation ratio of $O(\sqrt)$. This is not strong enough to refute the hypothesis; doing so would require finding an algorithm with a bounded approximation ratio.

Notes

References

{{reflist, refs=

{{citation, url=https://www.boazbarak.org/sos/prev/files/lec6.pdf, title=SOS Lecture 6: The SOS approach to refuting the UGC, first=Boaz, last=Barak, author-link=Boaz Barak, work=Lecture notes on "Proofs, beliefs and algorithms through the lens of Sum of Squares", year=2016, access-date=2023-03-14

{{citation
, last1 = Bafna , first1 = Mitali
, last2 = Barak , first2 = Boaz , author2-link = Boaz Barak
, last3 = Kothari , first3 = Pravesh K.
, last4 = Schramm , first4 = Tselil
, last5 = Steurer , first5 = David
, editor1-last = Khuller , editor1-first = Samir , editor1-link = Samir Khuller
, editor2-last = Williams , editor2-first = Virginia Vassilevska , editor2-link = Virginia Vassilevska Williams
, arxiv = 2006.09969
, contribution = Playing unique games on certified small-set expanders
, doi = 10.1145/3406325.3451099
, pages = 1629–1642
, publisher = Association for Computing Machinery
, title = STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021
, year = 2021

{{citation
, last1 = Bansal , first1 = Nikhil
, last2 = Feige , first2 = Uriel , author2-link = Uriel Feige
, last3 = Krauthgamer , first3 = Robert
, last4 = Makarychev , first4 = Konstantin
, last5 = Nagarajan , first5 = Viswanath
, last6 = Naor , first6 = Joseph , author6-link = Joseph Seffi Naor
, last7 = Schwartz , first7 = Roy
, doi = 10.1137/120873996
, issue = 2
, journal = SIAM Journal on Computing
, mr = 3504685
, pages = 872–904
, title = Min-max graph partitioning and small set expansion
, url = https://www.wisdom.weizmann.ac.il/~robi/papers/BFKMNNS-MinMaxCuts-SICOMP14.pdf
, volume = 43
, year = 2014

{{citation
, last1 = Feige , first1 = Uriel , author1-link = Uriel Feige
, last2 = Hajiaghayi , first2 = Mohammadtaghi , author2-link = Mohammad Hajiaghayi
, last3 = Lee , first3 = James R.
, doi = 10.1137/05064299X
, issue = 2
, journal = SIAM Journal on Computing
, mr = 2411037
, pages = 629–657
, title = Improved approximation algorithms for minimum weight vertex separators
, volume = 38
, year = 2008

{{citation
, last1 = Gandhi , first1 = Rajiv
, last2 = Kortsarz , first2 = Guy
, doi = 10.1016/j.dam.2015.05.028
, journal = Discrete Applied Mathematics
, mr = 3391764
, pages = 93–101
, title = On set expansion problems and the small set expansion conjecture
, url = https://sites.rutgers.edu/guy-kortsarz/wp-content/uploads/sites/855/2022/07/On-edge-expansion-problems-and-the-small-set-expansion-conjecture.pdf
, volume = 194
, year = 2015

{{citation, url=https://www.nasonline.org/programs/awards/2018/Raghavendra-Steurer.html, title=2018 Michael and Sheila Held Prize: Prasad Raghavendra and David Steurer, publisher=National Academy of Sciences, access-date=2023-11-23

{{citation
, last = Manurangsi , first = Pasin
, arxiv = 1705.03581
, doi = 10.3390/a11010010
, issue = 1
, journal = Algorithms
, mr = 3758880
, page = P10:1–P10:22
, title = Inapproximability of maximum biclique problems, minimum {{mvar, k-cut and densest at-least-{{mvar, k-subgraph from the small set expansion hypothesis
, volume = 11
, year = 2018
, doi-access = free

{{citation
, last1 = Raghavendra , first1 = Prasad
, last2 = Steurer , first2 = David
, editor-last = Schulman , editor-first = Leonard J.
, contribution = Graph expansion and the unique games conjecture
, doi = 10.1145/1806689.1806792
, pages = 755–764
, publisher = Association for Computing Machinery
, title = Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010
, url = https://people.eecs.berkeley.edu/~prasad/Files/expansion.pdf
, year = 2010, s2cid = 1601199

{{citation
, last1 = Raghavendra , first1 = Prasad
, last2 = Steurer , first2 = David
, last3 = Tulsiani , first3 = Madhur
, arxiv = 1011.2586
, contribution = Reductions between expansion problems
, doi = 10.1109/CCC.2012.43
, pages = 64–73
, publisher = IEEE Computer Society
, title = Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26–29, 2012
, year = 2012

{{citation
, last1 = Wu , first1 = Yu
, last2 = Austrin , first2 = Per
, last3 = Pitassi , first3 = Toniann , author3-link = Toniann Pitassi
, last4 = Liu , first4 = David
, doi = 10.1613/jair.4030
, journal = Journal of Artificial Intelligence Research
, mr = 3195329
, pages = 569–600
, title = Inapproximability of treewidth, one-shot pebbling, and related layout problems
, volume = 49
, year = 2014, doi-access = free

Computational hardness assumptions