Polynomial-bit treewidth recognition with a recursive witness table
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.certified_tight_block_searchalgorithmsclusteringdynamic-programming
For each fixed width, a binary algorithm decides whether the explicit graph has that treewidth bound. On positive inputs it supplies a finite policy covering every initial component and every child of a successful bag choice.
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.certified_tight_block_search (t : ℕ) :
Poly (policy t) ∧ Poly (decideWidth t) ∧ ∀z : GraphInput,
(decideWidth t z=true ↔ TreewidthLE (scopeGraph z.1 z.2) t) ∧
(TreewidthLE (scopeGraph z.1 z.2) t → Presents z t (policy t z)) := 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.