Finite-domain clique factors, exact-count witnesses, and treewidth promises
DefinitionStableMSR_Recovery_Supplement_CliqueFactorsalgorithmsclustering
A selection supplies one domain value per variable. Locality is invariance under agreement on the named scope. Each factor emits a list, and witnesses retain their exact total count and additive cost.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalTables
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
abbrev Value := List BallCode
abbrev Plan := List Value
def pickValue (vs : Block) (s : Plan) (v : ℕ) : Value := s[vs.idxOf v]?.getD []
def AllowedPlan (vs : Block) (ds : List Value) (s : Plan) : Prop :=
∀ v∈vs, pickValue vs s v∈ds
def DependsOn (vs scope : Block) (emit : Plan→Pack) : Prop :=
∀ s u, (∀ v∈scope,pickValue vs s v=pickValue vs u v) → emit s=emit u
def ScopeWidth (vs : Block) (scopes : List Block) (t : ℕ) : Prop :=
∃ (X : Type) (_ : Fintype X) (_ : DecidableEq X) (g : SimpleGraph X) (name : X→ℕ),
Function.Injective name ∧ (∀v, v∈vs ↔ ∃x, name x=v) ∧
RobertsonSeymour1986.GM5.TreewidthLE g t ∧ ∀ s∈scopes,
(∀v∈s,v∈vs) ∧ ∀x y, name x∈s → name y∈s → x≠y → g.Adj x y
def renderFactors (ids : Block) (emit : ℕ→Plan→Pack) (s : Plan) : Pack :=
ids.flatMap (fun j => emit j s)
def packCost (cost : Block→ℚ) (p : Pack) := (p.map cost).sum
def FactorRow (vs : Block) (ds : List Value) (build : Plan→Pack) (cost : Block→ℚ) (row : Table) : Prop :=
(∀ p∈row, ∃ s, AllowedPlan vs ds s ∧ build s=p) ∧
∀ s, AllowedPlan vs ds s → ∃ p∈row, p.length=(build s).length ∧ packCost cost p≤packCost cost (build s)
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
Finite-domain bounded-treewidth optimization with exact cardinalities and witnesses. See Ravichandran and Reyzin, Appendix A.6 (https://arxiv.org/abs/2611.03547) and Freuder, Complexity of k-tree structured constraint satisfaction problems, AAAI 1990.