The decoded separator bags cover all edges and have connected occurrences
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layered_bags_have_parent_certificatealgorithmsclusteringdynamic-programming
Place each live component at the least input position belonging to it. Adjacent vertices meet in the later home bag. Each occurrence away from home is a boundary vertex shared with the preceding bag. Blank slots are leaves of the root.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BlockTraceSemantics open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layered_bags_have_parent_certificate (z : GraphInput) (t : ℕ) (rs : List Rule) (cert : Presents z t rs) (facts : TraceFacts z rs)
(level : Vertex z→ℕ) (homes : HomeLevels z rs level) :
ParentCertificate z t (traceKeys z) (traceParent z rs) (traceBag z rs) := by
sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.