Threshold connectivity by a bounded binary label-merging sweep
DefinitionStableMSR_Recovery_Supplement_ThresholdComponentsalgorithmsclusteringdynamic-programming
Explicit polynomial-size component labels, component seeds, and the wide-component condition in the many-large-cluster branch.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_RegionRepair
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
open BinaryVerifier
def thresholdEdges (a : Input) (R : ℚ) : List BallCode :=
(ballCodes a).filter (fun e => decide (distAt a.1 a.2.2 e.1 e.2≤R))
def unify (ls : List ℕ) (e : BallCode) : List ℕ :=
ls.map (fun c => if c=numAt ls e.2 then numAt ls e.1 else c)
def componentLabels (a : Input) (R : ℚ) : List ℕ := (thresholdEdges a R).foldl unify (points a)
def componentPieces (a : Input) (R : ℚ) : Pack :=
let ls := componentLabels a R
(points a).map fun i => (points a).filter (fun j => decide (numAt ls i=numAt ls j))
def componentSeeds (a : Input) : List Scenario :=
(0::a.2.2).map fun R => (R,normalize a (componentPieces a R))
def Wide (I : RationalInput) (O : Partition I.n) (γ : ℚ) : Prop :=
∃ x y : Fin I.n, (thresholdGraph I.dist (largestRadius I.dist O) Finset.univ).Reachable x y ∧
densityScale I.dist O ((γ:ℝ)-1) < I.dist x y
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
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