corollaryroutine

Constant-factor hardness for cut and clustering problems

So cut and clustering problems are NP-hard to approximate within any constant

payoff of the main theorem

Corollary·cor:cut-clustering·§8.3 Cut, deletion, and clustering consequences

Statement (paper)

For every fixed real constant

C>1

, it is NP-hard to approximate each of the four minimization problems above within factor

C

. For \textsc{Sparsest Cut}, this is hardness of the search task under polynomial-time Cook reductions: the algorithm must output a cutset, not only an estimate of the optimum. Consequently, unless

\mathrm P=\mathrm{NP}

, none of these problems admits a deterministic polynomial-time approximation with any fixed constant factor.

In plain English

For every fixed constant

C>1

, each of the four minimization problems in this section (including Sparsest Cut) is NP-hard to approximate within factor

C

. For Sparsest Cut this holds for the search task under polynomial-time Cook reductions, where the algorithm must output a cutset. Hence unless P=NP, none of these problems has a deterministic polynomial-time constant-factor approximation.

Why it's here

This corollary transfers the gap in the Unique Games Theorem to the cut, deletion and clustering problems, so that satisfiable and unsatisfiable 3SAT formulas map to instances whose optima differ by more than factor

C

. Any constant-factor approximation would then decide 3SAT, which gives the P=NP conclusion.

Classified routine:

Follows from the Unique Games Theorem via the known UG-hardness reductions for Multicut, Sparsest Cut, Min-2CNF-Deletion and Correlation Clustering (Khot–Vishnoi 2005; Chawla–Krauthgamer–Kumar–Rabani–Sivakumar 2006), with the conditional statements becoming unconditional NP-hardness.

Uses

thmThe Unique Games Theorem

Used by

Nothing in the paper

Sources

PaperOpen

Section: §8.3 Cut, deletion, and clustering consequences
Page: —
Label: cor:cut-clustering
Line: sections/07-consequences.tex:261

Leannot aligned

Phase 2 aligns this node to a Lean declaration.