Theorem 1.2 — both constrained-clustering hardness thresholds
OpenConstrainedCorrelationRepulsion.Main.Supplement.theorem_1_2approximationcorrelation-clusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed real , constrained correlation clustering is NP-hard to approximate within , and assuming the Unique Games Conjecture it is NP-hard to approximate within :
Here hardness means actual polynomial-time reductions from every NP language to explicit feasible minimization gaps. Both clauses already hold on the cluster-deletion subclass , . Requested factors at or below one retain the monotone approximation-task meaning using a harder, nonoverlapping gap; no upper bound on is imposed. The cited external vertex-cover hardness results are proof dependencies and are not additional hypotheses of this theorem. This supplies the hardness side of the paper's approximation threshold.
Differences from the source:
- encoding: NP-hardness within each stated factor → explicit polynomial reductions to a fixed harder separated gap on the cluster-deletion subclass; reason: the source proves hardness on this subclass; choosing an intermediate factor and monotonicity covers every positive accuracy without overlapping promise sets
Preamble
import Definitions.Def_ConstrainedCorrelationRepulsion_Main_Supplement_Hardness
Formal statement
namespace ConstrainedCorrelationRepulsion.Main.Supplement
/-- Both clauses of Theorem 1.2. External vertex-cover hardness results are proof
dependencies, never extra hypotheses. The reductions already land in cluster deletion. -/
theorem theorem_1_2 (epsilon : ℝ) (hepsilon : 0 < epsilon) :
ApproximationNPHard (Real.sqrt 2 - epsilon) ∧
(OptInapprox.MaxCut.UGC → ApproximationNPHard (2 - epsilon)) := by sorry
end ConstrainedCorrelationRepulsion.Main.Supplement
Source
Yixin Cao, Ying Xu, STOC 2027 submission #869 (October 2026), Theorem 1.2, printed p.1 (PDF p.2), repeated statement and proof printed p.37 (PDF p.38)