First-fit ownership covers every factor scope
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.first_bag_covers_scopealgorithmsclusteringdynamic-programming
The variables of each factor form a clique, and a singleton is also a clique. The first bag containing that clique therefore exists and contains every listed occurrence.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BagMenuEncoding open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.first_bag_covers_scope (vs : Block) (scopes : List Block) (t : ℕ) (L : FactorLayout) (hl : GoodLayout vs scopes t L)
(S : Block) (hv : ∀v∈S,v∈vs) (hs : S∈scopes ∨ S.length≤1) :
owner L S<L.length ∧ ∀ v∈S,v∈bag L (owner L S) := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix A.6, tree-decomposition dynamic program. Explicit binary witness formulation.