A bounded progress bag for a tight connected region
ProvedStableMSR.Recovery.DecompositionSearch.exists_progress_bagLet a finite tree decomposition have bags of size at most . Let be a nonempty connected vertex set disjoint from , suppose one bag contains , and suppose every vertex of has a neighbor in . There exists a set satisfying
Moreover and . Thus a rooted tight boundary admits a candidate bag that makes strict recursive progress without increasing the width. This is a structural lemma for constructing a small tree decomposition; it does not assert that the complete search algorithm has been implemented.
Preamble
import Definitions.Def_SeymourThomas1993_Brambles import Definitions.Def_RobertsonSeymour1986_GM5_IsTreeDecomposition open RobertsonSeymour1986.GM5 StableMSR.Recovery.Havens
Formal statement
theorem StableMSR.Recovery.DecompositionSearch.exists_progress_bag {V T : Type} [DecidableEq V]
[Fintype T] [DecidableEq T] {G : SimpleGraph V} {tree : SimpleGraph T}
{bags : T → Finset V} (htd : IsTreeDecomposition G tree bags)
(S C : Finset V) (w : ℕ) (hC : ConnectedSet G C) (hdisj : Disjoint S C)
(hroot : ∃ r, S ⊆ bags r) (htouch : ∀ s ∈ S, ∃ c ∈ C, G.Adj s c)
(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 ∧ (C \ B).card < C.card := by sorrySource
Supporting construction lemma for Prove2Me mission Exact Sum-of-Radii Clustering under Any Constant Stability; derived from the Helly property of subtrees and the canonical tree-decomposition axioms.