Progress and exact child accounting in tight-boundary decomposition search
ProvedStableMSR.Recovery.DecompositionSearch.tight_block_progressLet a finite graph have a width- tree decomposition. Let be a component of with exact external boundary , and suppose some bag contains . There is a candidate bag with at most vertices that meets and is contained in an original bag. Its recursive child regions, the components of contained in , satisfy the exact accounting identity
Each child is a component after deleting its own exact boundary, that boundary is contained in and in an original bag, and
Also . This proves closure and strict progress of the intended finite-state decomposition search. The complete search recurrence, its reconstructed tree, and its instruction-level implementation are separate obligations.
Preamble
import Definitions.Def_StableMSR_TightBlockSearch open StableMSR.Recovery.DecompositionSearch StableMSR.Recovery.Havens open scoped BigOperators
Formal statement
theorem StableMSR.Recovery.DecompositionSearch.tight_block_progress {V : Type} [Fintype V] [DecidableEq V] {T : Type} [Fintype T] [DecidableEq T]
{G : SimpleGraph V} {tree : SimpleGraph T} {bags : T → Finset V}
(htd : RobertsonSeymour1986.GM5.IsTreeDecomposition G tree bags)
(S C : Finset V) (w : ℕ) (hC : IsFlap G S C)
(htight : boundary G C = S) (hroot : ∃ r, S ⊆ bags r)
(hwidth : ∀ t, (bags t).card ≤ w+1) :
∃ B : Finset V,
S ⊆ B ∧ B ⊆ S ∪ C ∧ B.card ≤ w+1 ∧ (B ∩ C).Nonempty ∧ S.card ≤ w ∧
(∃ t, B ⊆ bags t) ∧
(B ∩ C).card + (∑ D ∈ children G B C, D.card) = C.card ∧
∀ D ∈ children G B C,
IsFlap G (boundary G D) D ∧ boundary G D ⊆ B ∧
(boundary G D).card ≤ w ∧ D.card < C.card ∧
∃ r, boundary G D ⊆ bags r := by sorrySource
Supporting lemma for Prove2Me Exact Sum-of-Radii Clustering under Any Constant Stability; tight-boundary connected-component decomposition search and finite cardinality charging.