Uniform sparsest cut hardness and semidefinite gaps

← All digests

Family 117 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

A network can be difficult to divide even when a geometric relaxation suggests a cheap separation. Family 117 studies two distinct obstacles: the computational hardness of finding a near-optimal uniform sparsest cut, and the quantitative error of a standard semidefinite relaxation. Both claims preserve equal demand between every pair of vertices, a restriction that substantially changes the problem.

1. The question

A cut divides the vertices of a graph into two nonempty parts. Crossing edges represent connections disrupted by that division. Minimizing crossing capacity alone can isolate one inexpensive vertex, even when that is not a useful global separation.

Uniform sparsest cut divides the crossing capacity by the number of vertex pairs separated. For $n$ vertices and one side $S$, that number is $|S|(n-|S|)$.

The question is how cheaply the network can be divided relative to this all-pairs demand. Can a polynomial-time algorithm always return a cut within a fixed constant factor of the best one? And how closely does the standard vector relaxation track the true optimum?

The manuscripts claim a negative answer to constant-factor approximation under $\mathsf P\ne\mathsf{NP}$, and a nearly square-root-logarithmic separation between the relaxation and the actual cut value.

2. Background and essential definitions

Capacities, demands, and the objective

Let $c_{ij}=c_{ji}\ge0$ be the capacity between distinct vertices $i,j$. Missing edges can be assigned capacity zero. The objective is

$$\Phi(G)=\min_{\varnothing\ne S\subsetneq V} \frac{\sum_{i\in S,\,j\notin S}c_{ij}}{|S|(n-|S|)}.$$

Each crossing unordered pair is counted once in the numerator. The denominator gives unit demand to every distinct pair, regardless of whether it is an edge.

A factor-$C$ approximation must return an actual nonempty proper cut with value at most $C\Phi(G)$. The factor is multiplicative. A fixed additive error can be useless when the optimum is very small.

The nonuniform problem replaces the denominator by selected or weighted demands. Hardness or geometric obstructions for that broader problem do not automatically establish the uniform case.

Relax cuts into vector distances

A cut has a simple distance representation: assign zero to vertices on one side and one to those on the other. Distances are zero within a side and one across it.

The Goemans–Linial semidefinite relaxation permits more general distances

$$d(i,j)=\|v_i-v_j\|_2^2,$$

subject to every triangle inequality. Squared Euclidean distances do not automatically satisfy those inequalities, so that condition is essential. Distinct vertices may have distance zero, giving a semimetric.

After normalizing $\sum_{i<j}d(i,j)=1$, the relaxation minimizes $\sum_{i<j}c_{ij}d(i,j)$. Write its value as $\operatorname{GL}(G)$. Every normalized cut distance is feasible, hence

$$\operatorname{GL}(G)\le\Phi(G).$$

The integrality gap is the ratio $\Phi(G)/\operatorname{GL}(G)$ when the denominator is positive. A large gap says the relaxation can be too optimistic, even if solved exactly.

3. Development history and previous partial results

The flow–cut approach of Leighton and Rao linked graph partitioning to routing many simultaneous demands and gave logarithmic approximation guarantees. Linial, London, and Rabinovich developed the metric-embedding viewpoint connecting cuts with geometry.

Arora, Rao, and Vazirani, first presented in 2004, improved uniform sparsest-cut approximation to order $\sqrt{\log n}$ through semidefinite programming and geometric separation. That is the upper-bound benchmark for this family.

Exact NP-hardness does not by itself rule out a constant-factor approximation. Earlier strong approximation hardness for uniform sparsest cut used additional assumptions such as Small-Set Expansion, as reviewed in M1. Related Unique Games implications for nonuniform demands concern a different objective.

On the relaxation side, Devanur, Khot, Saket, and Vishnoi established a growing uniform-demand integrality gap of order $\log\log n$, disproving the constant-gap prediction. Kane and Meka obtained a stronger lower bound of the form $\exp(\Omega(\sqrt{\log\log n}))$.

For general demands, geometric work culminated in a square-root-logarithmic lower bound by Naor and Young, with matching upper bounds in later work of Chang, Naor, and Ren. But worst-pair distortion is not the same as preservation of average distances over every pair.

Rabinovich’s average-distortion framework identifies the relevant geometric quantity for uniform demands. The new gap manuscript addresses precisely that average-distance obstruction, rather than simply importing a general-demand example.

4. What the new manuscripts claim

M1 states that for every fixed $C>1$, a deterministic polynomial-time reduction maps a Boolean satisfiability instance to a rational-capacity graph and positive rational threshold $a$ such that

$$\begin{aligned} \text{satisfiable}&\implies\Phi(G)\le a,\\ \text{unsatisfiable}&\implies\Phi(G)>Ca. \end{aligned}$$

Every distinct vertex pair has demand exactly one. Graph size and number encodings are polynomial in the source input, with constants and polynomial degree allowed to depend on $C$.

Thus every fixed-factor approximation is NP-hard. The reduction itself uses no unproved complexity assumption; concluding that no polynomial-time approximation exists additionally assumes $\mathsf P\ne\mathsf{NP}$. The direct uniform-demand reduction is independent of the family’s cited nonuniform consequence of Unique Games.

M2 claims a sequence of instances on $n_j\to\infty$ vertices with positive relaxation value and

$$\frac{\Phi(G_j)}{\operatorname{GL}(G_j)} \ge c\frac{\sqrt{\log n_j}}{(\log\log n_j)^3}$$

for an absolute $c>0$. Its capacities are nonnegative real numbers and its demands are exactly uniform. The construction is stated along an infinite sequence of sizes, not as an instance for every integer size.

This approaches the square-root-logarithmic upper-bound scale up to an iterated-logarithmic factor. It concerns the basic Goemans–Linial relaxation, not every possible strengthened hierarchy.

5. Why the advance matters

Importance: 4/5, provisional. Sparsest cut is a central graph-partitioning problem with connections to flows, approximation algorithms, and metric geometry. The claims would strengthen both its computational hardness landscape and the quantitative understanding of its main geometric relaxation.

The two results answer different questions. An integrality gap identifies a limitation of one relaxation; it does not rule out a completely different algorithm. NP-hardness constrains all polynomial-time approximation methods under the usual complexity separation, but does not specify how inaccurate one relaxation can be.

Uniform demands make the advance more specific and meaningful. Every pair contributes, so a construction cannot concentrate all demand on a carefully chosen collection of difficult pairs. It must create an obstruction visible in the global average.

6. The main idea

Make even very small cuts meaningful

M1 builds a gap reduction from local tests of a proposed Boolean assignment. A satisfying assignment induces a cheap cut. Conversely, a sufficiently cheap cut must contain information that can be decoded into a satisfying assignment.

The difficult case is a cut with a tiny side. Its separated demand can be very small, so an absolute error allowance could overwhelm the quantity being compared. The construction tracks errors relative to the cut’s own demand, expressed through the variance of its zero–one indicator.

The paper uses rare events built from conjunctions of predicates, meaning yes-or-no tests on proof bits. A low comparison cost forces a signal from which a consistent Boolean valuation can be extracted. Different descriptions of the same predicate must receive the same valuation; this keeps the decoding tied to functions rather than arbitrary encodings.

Finally, rational approximations and replication convert probability masses into vertex counts. Heavy connections prevent a cheap cut from separating copies improperly. This produces the exact cardinality-product denominator rather than an approximately uniform demand model.

Build distances that cuts cannot preserve on average

M2 takes a geometric route. Finite distances arising from cuts can be combined into distances in $\ell_1$, where

$$\|z\|_1=\sum_i|z_i|.$$

A map is nonexpanding if it never increases pairwise distances. The construction seeks a squared-Euclidean semimetric with large average distance, but for which every nonexpanding map into $\ell_1$ has much smaller average distance.

It creates many rounded coordinate charts from a common parameter cube. Different charts describe the same underlying parameter values, forcing a candidate map to respect several compatible sets of local constraints.

Hilbert-space features give large global distances. A separate repair enforces all triangle inequalities while preserving carefully controlled small costs across neighboring cells. Both local and global estimates are necessary: a uniformly small absolute error could still destroy the tiny interface bounds.

The many charts then constrain gradients of smoothed versions of any $\ell_1$ map. Those gradient bounds limit the average distances the map can retain.

Convert geometry into a graph instance

The geometric probability measure is replaced by multiplicities of vertices, retaining every chart’s constraints. Uniform measure on the copies approximates the intended average while giving equal demand to each pair.

A finite-dimensional duality between cuts and capacities then produces the claimed graph instance. The geometric dimension-to-vertex-count conversion accounts for the displayed $(\log\log n)^3$ loss.

7. Scope, limitations, and open questions

The hardness factor is any fixed constant. The reduction’s degree may depend on that constant, so it does not automatically yield a quantitative hardness bound growing with $n$.

The gap theorem is existential with real capacities, whereas the hardness reduction supplies rational encodings in polynomial time. These are separate output guarantees.

The gap nearly reaches the known upper-bound order but leaves iterated-logarithmic slack. Removing that slack, understanding stronger relaxations, and obtaining more quantitative approximation-hardness rates are distinct further questions.

The family also leaves room for efficient algorithms on restricted graph classes or with additional promises. Worst-case hardness does not describe every network instance.

8. Sources and further reading

M1’s theorem specifies the reduction, capacity encoding, and every-cut scope. M2 defines its semidefinite relaxation explicitly and traces the average-distortion route to uniform demands. The historical papers linked above explain why computational hardness and geometric relaxation gaps must be assessed separately.

Source manuscripts

• M1. OpenAI, Constant-factor hardness of uniform sparsest cut (2026).
• M2. OpenAI, Near-square-root logarithmic integrality gaps for uniform sparsest cut (2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.