Decode an explicit tree decomposition from a tight-block witness table
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layout_from_tight_block_policyalgorithmsclusteringdynamic-programming
Given a finite table of successful tight-block bag choices with witnesses for every root and every child, select one choice per active interior and decode the recursive choices into a list of bags and edges in polynomial binary time.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_TightBlockPolicies 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 open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layout_from_tight_block_policy (t : ℕ) : ∃ A : GraphInput × List Rule → FactorLayout, Poly A ∧
∀ (z : GraphInput) (rs : List Rule), Presents z t rs → GoodLayout z.1 z.2 t (A (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.