Appendix A.6: clustering constraint supports lie in decomposition bags
ProvedStableMSR.Recovery.clustering_constraint_bag_placementLet be a finite metric, let , and let each candidate set lie within distance of its specified center . Assign it to an owner with . The interaction graph on joins distinct vertices at distance at most . Fix any finite tree decomposition of that graph.
Every point constraint fits in a single bag: for each input point , some bag contains all owners of candidates covering .
Every optional-component constraint also fits in a single bag: if an optional set has diameter at most , some bag contains all owners of candidates meeting .
The result holds for every candidate family passing these geometric conditions, independently of stability or optimality. In the source algorithm, optional components satisfy the stronger diameter bound . Thus this establishes the geometric support-containment hypothesis used to allocate the actual point predicates, optional-component predicates, and optional-component count/cost contributions to bags. It assumes a tree decomposition as input; constructing that decomposition and compiling the DP are separate obligations.
import Definitions.Def_StableMSR_Recovery_Geometry import Definitions.Def_RobertsonSeymour1986_GM5_IsTreeDecomposition set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery
theorem clustering_constraint_bag_placement {n : ℕ} {I T : Type}
[Fintype T] [DecidableEq T]
(d : Point n → Point n → ℝ) (hd : IsMetricArray d) (R : ℝ) (hR : 0 ≤ R)
(N : Cluster n) (pool : Finset I) (candidate : I → Cluster n)
(center : I → Point n) (owner : I → N)
(howner : ∀ i ∈ pool, d (owner i) (center i) ≤ 2 * R)
(hcandidate : ∀ i ∈ pool, ∀ x ∈ candidate i, d (center i) x ≤ R)
(optional : Partition n) (hdiam : ∀ K ∈ optional, diameter d K ≤ 2 * R)
(tree : SimpleGraph T) (bags : T → Finset N)
(htd : RobertsonSeymour1986.GM5.IsTreeDecomposition
((thresholdGraph d (8 * R) N).induce (N : Set (Point n))) tree bags) :
(∀ x : Point n, ∃ t : T, ∀ i ∈ pool, x ∈ candidate i → owner i ∈ bags t) ∧
(∀ K ∈ optional, ∃ t : T, ∀ i ∈ pool,
(candidate i ∩ K).Nonempty → owner i ∈ bags t) := by sorry
end StableMSR.Recovery