Small set expansion hypothesis

Last updated January 08, 2024

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 {|\partial X|}{|X|}},

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.^{[lower-alpha 1]} 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$ .^[1]^[2]

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.^{[lower-alpha 2]} 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.^[1]^{[lower-alpha 3]}

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 $d$ -regular graphs with small set expansion at least $(1-\varepsilon )d$ (good small set expanders), and $d$ -regular 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.^[1]^{[lower-alpha 3]}

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.^[1]

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.^[1]^[2] Boaz Barak has suggested more strongly that these two hypotheses are equivalent.^[1] 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.^[3] 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.^[4]

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 {\log w}})$ .^[5] The small set expansion hypothesis, if true, implies that there does not exist an approximation algorithm for this problem with constant approximation ratio.^[6] 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.^[7]

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.^[8]

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,^[2] 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.^[9]

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 {\log n\log \log n}})$ . This is not strong enough to refute the hypothesis; doing so would require finding an algorithm with a bounded approximation ratio.^[10]

Notes

↑ This definition follows the notation used in the expander graph article; some sources, such as Raghavendra & Steurer (2010), instead normalize the edge expansion by dividing it by the degree of the graph.
↑ This definition avoids using subsets whose number of vertices is close to $n$ , because these subsets would have small expansion even in graphs that otherwise have high expansion.
1 2 This formulation is from Barak (2016), who notes that it eliminates some unimportant parameters appearing in other formulations of the same hypothesis, such as that in Raghavendra & Steurer (2010).

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

<span class="mw-page-title-main">Set cover problem</span> Classical problem in combinatorics

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant $such that the worst-case running time of the algorithm, on inputs of size, has an upper bound of the form$

In mathematics, the minimum $k$ -cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least $k$ connected components. These edges are referred to as $k$ -cut. The goal is to find the minimum-weight $k$ -cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, $. More precisely, the usual form of the hypothesis asserts the existence of a number such that all algorithms that correctly solve this problem require time at least . The exponential time hypothesis, if true, would imply that P \neq NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity.$

In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, a constant positive relative distance, and a constant alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let $G = (V, E)$ be an undirected graph and let $S = (V S, E S)$ be a subgraph of $G$ . Then the density of $S$ is defined to be:

In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.

References

1 2 3 4 5 6 Barak, Boaz (2016), "SOS Lecture 6: The SOS approach to refuting the UGC" (PDF), Lecture notes on "Proofs, beliefs and algorithms through the lens of Sum of Squares", retrieved 2023-03-14
1 2 3 Raghavendra, Prasad; Steurer, David (2010), "Graph expansion and the unique games conjecture", in Schulman, Leonard J. (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 (PDF), Association for Computing Machinery, pp. 755–764, doi:10.1145/1806689.1806792, S2CID 1601199
↑ Raghavendra, Prasad; Steurer, David; Tulsiani, Madhur (2012), "Reductions between expansion problems", Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26–29, 2012, IEEE Computer Society, pp. 64–73, arXiv: 1011.2586 , doi:10.1109/CCC.2012.43
↑ Bafna, Mitali; Barak, Boaz; Kothari, Pravesh K.; Schramm, Tselil; Steurer, David (2021), "Playing unique games on certified small-set expanders", in Khuller, Samir; Williams, Virginia Vassilevska (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021, Association for Computing Machinery, pp. 1629–1642, arXiv: 2006.09969 , doi:10.1145/3406325.3451099
↑ Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R. (2008), "Improved approximation algorithms for minimum weight vertex separators", SIAM Journal on Computing , 38 (2): 629–657, doi:10.1137/05064299X, MR 2411037
↑ Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014), "Inapproximability of treewidth, one-shot pebbling, and related layout problems", Journal of Artificial Intelligence Research , 49: 569–600, doi: 10.1613/jair.4030 , MR 3195329
↑ Manurangsi, Pasin (2018), "Inapproximability of maximum biclique problems, minimum $k$ -cut and densest at-least- $k$ -subgraph from the small set expansion hypothesis", Algorithms, 11 (1): P10:1–P10:22, arXiv: 1705.03581 , doi: 10.3390/a11010010 , MR 3758880
↑ Gandhi, Rajiv; Kortsarz, Guy (2015), "On set expansion problems and the small set expansion conjecture" (PDF), Discrete Applied Mathematics , 194: 93–101, doi:10.1016/j.dam.2015.05.028, MR 3391764
↑ 2018 Michael and Sheila Held Prize: Prasad Raghavendra and David Steurer, National Academy of Sciences, retrieved 2023-11-23
↑ Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy (2014), "Min-max graph partitioning and small set expansion" (PDF), SIAM Journal on Computing , 43 (2): 872–904, doi:10.1137/120873996, MR 3504685

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] This definition follows the notation used in the expander graph article; some sources, such as Raghavendra & Steurer (2010), instead normalize the edge expansion by dividing it by the degree of the graph.

[4] This definition avoids using subsets whose number of vertices is close to $n$ , because these subsets would have small expansion even in graphs that otherwise have high expansion.

[barak-5] 1 2 This formulation is from Barak (2016), who notes that it eliminates some unimportant parameters appearing in other formulations of the same hypothesis, such as that in Raghavendra & Steurer (2010).

[barak-2] 1 2 3 4 5 6 Barak, Boaz (2016), "SOS Lecture 6: The SOS approach to refuting the UGC" (PDF), Lecture notes on "Proofs, beliefs and algorithms through the lens of Sum of Squares", retrieved 2023-03-14

[rs-3] 1 2 3 Raghavendra, Prasad; Steurer, David (2010), "Graph expansion and the unique games conjecture", in Schulman, Leonard J. (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 (PDF), Association for Computing Machinery, pp. 755–764, doi:10.1145/1806689.1806792, S2CID 1601199

[rst-6] Raghavendra, Prasad; Steurer, David; Tulsiani, Madhur (2012), "Reductions between expansion problems", Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26–29, 2012, IEEE Computer Society, pp. 64–73, arXiv: 1011.2586 , doi:10.1109/CCC.2012.43

[bbk-7] Bafna, Mitali; Barak, Boaz; Kothari, Pravesh K.; Schramm, Tselil; Steurer, David (2021), "Playing unique games on certified small-set expanders", in Khuller, Samir; Williams, Virginia Vassilevska (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021, Association for Computing Machinery, pp. 1629–1642, arXiv: 2006.09969 , doi:10.1145/3406325.3451099

[fhl-8] Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R. (2008), "Improved approximation algorithms for minimum weight vertex separators", SIAM Journal on Computing , 38 (2): 629–657, doi:10.1137/05064299X, MR 2411037

[wapl-9] Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014), "Inapproximability of treewidth, one-shot pebbling, and related layout problems", Journal of Artificial Intelligence Research , 49: 569–600, doi: 10.1613/jair.4030 , MR 3195329

[manurangsi-10] Manurangsi, Pasin (2018), "Inapproximability of maximum biclique problems, minimum $k$ -cut and densest at-least- $k$ -subgraph from the small set expansion hypothesis", Algorithms, 11 (1): P10:1–P10:22, arXiv: 1705.03581 , doi: 10.3390/a11010010 , MR 3758880

[gs-11] Gandhi, Rajiv; Kortsarz, Guy (2015), "On set expansion problems and the small set expansion conjecture" (PDF), Discrete Applied Mathematics , 194: 93–101, doi:10.1016/j.dam.2015.05.028, MR 3391764

[held-12] 2018 Michael and Sheila Held Prize: Prasad Raghavendra and David Steurer, National Academy of Sciences, retrieved 2023-11-23

[bfk-13] Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy (2014), "Min-max graph partitioning and small set expansion" (PDF), SIAM Journal on Computing , 43 (2): 872–904, doi:10.1137/120873996, MR 3504685

[lower-alpha 1]

[1]

[2]

[lower-alpha 2]

[lower-alpha 3]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]