Uniform sparsest cut: hardness and semidefinite gaps

1 · The essentials

Uniform Sparsest Cut asks how to split a network into two groups while keeping the total weight of connections cut small relative to the number of pairs separated. Every pair of distinct points counts equally. The first manuscript shows that finding a split guaranteed to be within any fixed factor greater than one of the best possible value is computationally hard in the sense made precise below. This holds even when all connection weights are nonnegative rational numbers. The second manuscript constructs networks on which a particular mathematical shortcut gives an increasingly overoptimistic estimate of the best split. That second result has a Lean formalization; the supplied source does not identify the first manuscript’s hardness result as formalized.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine dividing people into two rooms, with a cost for each connection between people placed in different rooms, and judging that cost relative to how many pairs you separate. The two manuscripts distinguish the difficulty of finding a near-best division from the risk that a simplified planning calculation reports a value far better than any actual division can achieve.

Why it matters

The family identifies two distinct obstacles: computational hardness for every fixed approximation factor greater than one, and a growing discrepancy in the Goemans–Linial semidefinite relaxation. The latter discrepancy comes close to the stated Arora–Rao–Vazirani upper bound, differing by a power of $lo g lo g n$ .

2 · Going further

Uniform Sparsest Cut concerns a graph with capacities on its connections and unit demand between every pair of distinct vertices. A cut partitions the vertices into two groups, and its quality compares the capacity crossing the partition with the demand it separates. The first manuscript shows that, for every fixed $C > 1$ , approximation within factor $C$ is NP-hard. Its output graphs have nonnegative rational capacities and unit demands.

The companion manuscript studies the Goemans–Linial semidefinite relaxation, which replaces the cut problem with a relaxed optimization problem. It constructs instances whose integrality gap—the ratio between the true cut optimum and the relaxation optimum—is at least $c lo g n / (lo g lo g n)^{3}$ along a sequence $n \to \infty$ . Here the capacities are nonnegative real numbers, and demands remain one between every pair of distinct vertices.

The supplied abstract describes the gap argument as a construction of instances, but gives no details of that construction or of the hardness argument. It states that the gap matches the Arora–Rao–Vazirani upper bound up to a power of $lo g lo g n$ . Thus the manuscripts address complementary questions: how hard approximation is, and how far this particular relaxation can underestimate the true optimum. The gap manuscript is identified as Lean-formalized; that verification status should not be extended to the separate hardness manuscript.

Useful notions

Graphs and weighted connections
Partitions and cuts
Optimization and approximation factors
NP-hardness
Relaxations and integrality gaps

What was known before / what is new

Before

The source names the Arora–Rao–Vazirani upper bound as the benchmark for the integrality-gap result. The repository summary describes this benchmark as square-root-logarithmic. No further historical context or earlier hardness results are supplied.

New

The first manuscript shows NP-hardness of approximation within every fixed factor $C > 1$ , with nonnegative rational capacities and unit demands. The Lean-formalized companion constructs a sequence of instances with gap at least $c lo g n / (lo g lo g n)^{3}$ . Its capacities are nonnegative real numbers, rather than the rational capacities specified for the hardness result.

Limits and assumptions

The hardness statement concerns each fixed factor $C > 1$ and graphs with nonnegative rational capacities and unit demands. The gap lower bound concerns a sequence of sizes tending to infinity, not an explicitly stated guarantee for every size, and allows nonnegative real capacities. Lean formalization is identified for the integrality-gap manuscript, not for the hardness manuscript or every claim in the family. A power of $lo g lo g n$ still separates the stated lower bound from the cited upper bound; the source does not explicitly list further open problems or provide the arguments’ technical details.

Mini glossary

Unit demand: A requirement that every pair of distinct vertices contributes the same demand, equal to one.
Approximation factor: For this minimization problem, a factor $C$ means a solution value no greater than $C$ times the optimum.
NP-hardness: A complexity classification expressing that a problem is at least as hard as problems in NP under the relevant reductions.
Semidefinite relaxation: A replacement optimization problem using semidefinite constraints that permits more possibilities than the original cut problem.
Integrality gap: The ratio between the original minimization problem’s optimum and its relaxation’s optimum.
Lean formalization: A representation of a mathematical result and its proof in the Lean proof-assistant system for machine checking.

Keywords : Uniform Sparsest Cut · NP-hardness · Integrality gaps

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves that approximating Uniform Sparsest Cut within any fixed constant factor is NP-hard, even with nonnegative rational capacities and unit demands. The Goemans–Linial semidefinite relaxation also has integrality gaps of order at least $lo g n / (lo g lo g n)^{3}$ , approaching the square-root-logarithmic upper bound.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/117.md

Manuscripts in this family

★

Constant-factor hardness of uniform sparsest cut

24/09/2026

To be verified

We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.

PDF GitHub folder

Near-square-root logarithmic integrality gaps for uniform sparsest cut

24/09/2026

Verified by Lean

We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least $c lo g n / (lo g lo g n)^{3}$ along a sequence $n \to \infty$ . The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of $lo g lo g n$ .

PDF GitHub folder Lean formalization