Small-Set Expansion hypothesis

A network can contain a group that is tightly linked inside but barely connected to the rest. For example, choose four nodes in a twenty-node graph where every node has three links. If five links are internal to the group and two lead out, only two of its twelve link ends lead outside: an outward fraction of one sixth. More generally, links can carry weights, with each node having the same total link weight. The hypothesis asks whether it is computationally hard to distinguish a graph with a nearly isolated small group from one where every group of that same prescribed size sends almost all its links outward. The input is promised to have one of those two properties.[1] [2]

Is detecting a small, nearly isolated vertex group computationally hard even when the alternative is that every group of exactly that size sends almost all its edge weight outside? Work with regular weighted undirected graphs: each vertex has the same positive total incident weight $D$. For a set $S$, volume is its fraction of total weighted degree, and expansion is its outward weight divided by its own weighted degree:$$\mu(S)=\frac{D|S|}{D|V|}=\frac{|S|}{|V|},\qquad \Phi(S)=\frac{w(S,V\setminus S)}{D|S|}.$$Here $w(S,V\setminus S)$ counts each crossing edge once from its endpoint in $S$. In the unweighted twenty-vertex example with degree three, four chosen vertices have five internal edges and two crossing edges: $\mu(S)=1/5$ and $\Phi(S)=2/(3\cdot4)=1/6$. This is a counting example, not a hardness construction. The hypothesis says that for every fixed $\eta\in(0,1/2)$, some fixed $\delta\in(0,1)$ makes the following promise problem NP-hard: distinguish existence of a set with $\mu(S)=\delta,\Phi(S)\le\eta$ from $\Phi(S)\ge1-\eta$ for every set with $\mu(S)=\delta$. Choose $\delta$ after $\eta$, independently of graph size; sizes must admit that exact volume.[1] [2]

The conjectured hardness remains unproved.[2]

The standard quantifiers fix δ after η. Conditional consequences and randomized-hardness variants do not establish this original NP-hardness promise.[2]

A sparse boundary can identify a part of a network that is relatively separated from the rest. Searching for such parts is central to graph partitioning. The hypothesis would give a reason why some approximation guarantees are hard to achieve: even telling a very good small group from uniformly poor groups could encode other difficult decision problems. The stakes concern the best possible algorithms and their guarantees, rather than the failure of one clustering method.[1] [2]

The promise builds a large gap into a normalized partitioning objective. A reduction can turn finding or approximating useful graph cuts into distinguishing the two cases, transferring the hypothesized obstacle to other problems. The original work uses this route to obtain conditional approximation hardness for Balanced Separator and Minimum Linear Arrangement, respectively splitting a graph into balanced parts and ordering its vertices on a line while keeping connected vertices close together. NP-hardness means that other NP decision problems reduce to this promise problem; a polynomial-time solution would therefore imply $\mathrm P=\mathrm{NP}$. This is the standard hardness target, distinct from assuming directly that even randomized polynomial-time algorithms cannot solve the weighted exact-volume promise.[1] [2]