Binary polynomial-time component labeling at every rational metric threshold
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.threshold_components_binaryalgorithmsclusteringcomputational-complexity
Enumerate threshold edges, initially label each point by itself, and merge two entire label classes for every edge. The resulting equivalence relation is exactly graph reachability. On arbitrary binary data the sweep has polynomial encoded size, even for malformed dimensions.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_ThresholdComponents import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.threshold_components_binary :
Poly (fun z : Input × ℚ => componentLabels z.1 z.2) ∧
∀ (I : RationalInput) (_ : I.Valid) (R : ℚ), let ls := componentLabels (fieldsOf I) R
ls.length=I.n ∧ ∀ x y : Fin I.n, BinaryVerifier.numAt ls x.val=BinaryVerifier.numAt ls y.val ↔
(thresholdGraph I.dist (R:ℝ) Finset.univ).Reachable x y := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 4.1 equation (2), Proposition 4.2 and Appendices A.4–A.6. https://arxiv.org/abs/2611.03547