Compute an encoded tree decomposition for the primal graph
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_width_layout_searchalgorithmsclusteringdynamic-programming
For fixed width, compute a list of bags and edges forming a width-t tree decomposition whenever the explicit co-occurrence graph has treewidth at most t. The input includes every variable name, including isolated ones.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_FactorLayouts import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.bounded_width_layout_search (t : ℕ) : ∃ A : Block × List Block → FactorLayout, Poly A ∧ ∀ vs scopes,
TreewidthLE (scopeGraph vs scopes) t → GoodLayout vs scopes t (A (vs,scopes)) := by
sorry
Source
Binary counterpart of StableMSR.Recovery.DecompositionSearch.polynomial_size_table_search.