Uniform polynomial approximation on the must-link-only domain
DefinitionConstrainedCorrelationRepulsion_Main_Supplement_MustLinkscorrelation-clusteringhard-constraintsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a ratio , the must-link-only approximation predicate asserts the existence of one finite randomized program and positive natural constants that work for every vertex count and every feasible complete unweighted instance whose cannot-link graph is empty. It requires the published operational guarantee
Every supported output is feasible, including on empty and singleton inputs. Runtime is charged by the existing fair-coin bit-cost interpreter; neither an optimal partition nor an arbitrary good-output distribution is an input. Must-links and signs are unrestricted. The condition is , rather than the existing only-cannot-links flag, which instead enforces .
Differences from the source:
- encoding: randomized polynomial-time approximation with must-links only → the published operational approximation predicate uniformly over ; reason: feasibility holds for every supported output and all polynomial constants precede the inputs.
Definition code
import Definitions.Def_ConstrainedCorrelationRepulsion_Main_Algorithm
namespace ConstrainedCorrelationRepulsion.Main.Supplement
/-- The H-empty domain. One finite fair-coin bit-cost program and one polynomial work on
all feasible inputs; no bound on must-link components, n, signs or accuracy is imposed. -/
def MustLinkApproximation (ratio : ℝ) : Prop :=
∃ code : Program, ∃ C d : ℕ, 0 < C ∧ 0 < d ∧
∀ n (I : Instance n), FeasibleInput I → I.cannotLink = ⊥ →
Approximates code I ratio (polynomialBound C d n)
end ConstrainedCorrelationRepulsion.Main.Supplement
Source
Yixin Cao, Ying Xu, STOC 2027 submission #869 (October 2026), Theorem 1.5, printed pp.2, 16 (PDF pp.3, 17)