Parent pointers and connected bag occurrences certify a tree decomposition
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.parent_certificate_is_tree_decompositionalgorithmsclusteringdynamic-programming
Strictly decreasing depth gives a connected tree. Each occurrence of a graph vertex connects through its parents to its distinguished home bag. This gives the native running-intersection property for the encoded layout.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_ParentBagCertificates 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.parent_certificate_is_tree_decomposition (z : GraphInput) (t : ℕ) (ks : List Key) (up : Key→Key) (bag : Key→Block)
(cert : ParentCertificate z t ks up bag) : GoodLayout z.1 z.2 t (parentLayout ks up bag) := 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.