An exact binary DP plan for every finite tree decomposition
ProvedStableMSR.Recovery.TreeDP.binary_plan_from_decompositionLet a finite tree decomposition have bags, a specified root, and a local record at each bag. Each record specifies finitely many allowed assignments, a validity predicate, a nonnegative integer count and a real weight, all contributions depending only on the bag. Suppose every bag has at most variables and at most assignment choices. There is a coherent binary plan such that
Its root bag and choices are unchanged, it covers every variable, and every record still has at most variables and choices. For every global assignment, validity and local representability hold in the plan exactly when they hold at all original bags. The total count and weight equal the respective sums over the original bags. Thus binary conversion introduces neither duplicated contributions nor spurious restrictions. This statement concerns the finite representation; finding a small decomposition and compiling the DP into the recovery interpreter are separate obligations.
import Definitions.Def_StableMSR_BinaryTreeDP_Plan import Definitions.Def_RobertsonSeymour1986_GM5_IsTreeDecomposition import Mathlib.Data.Finset.Card open StableMSR.Recovery.TreeDP open scoped BigOperators
theorem StableMSR.Recovery.TreeDP.binary_plan_from_decomposition {V X T : Type} [DecidableEq V]
[Fintype T] [DecidableEq T] (G : SimpleGraph V) (tree : SimpleGraph T)
(data : T → BagData V X)
(htd : RobertsonSeymour1986.GM5.IsTreeDecomposition G tree (fun t => (data t).bag))
(root : T) (width choices : ℕ)
(hlocal : ∀ t, (data t).Local)
(hbound : ∀ t, (data t).bag.card ≤ width ∧ (data t).choices.card ≤ choices) :
∃ p : Plan V X,
p.Coherent ∧ p.Local ∧ p.root.bag = (data root).bag ∧
p.root.choices = (data root).choices ∧
(∀ v, v ∈ p.scope) ∧
(∀ whole : V → X,
(p.AllValid whole ↔ ∀ t, (data t).valid whole) ∧
(p.AllData (fun d => ∃ a ∈ d.choices, AgreeOn d.bag whole a) ↔
∀ t, ∃ a ∈ (data t).choices, AgreeOn (data t).bag whole a) ∧
p.totalCount whole = ∑ t, (data t).count whole ∧
p.totalWeight whole = ∑ t, (data t).weight whole) ∧
p.nodes + 1 = 2 * Fintype.card T ∧
p.AllData (fun d => d.bag.card ≤ width ∧ d.choices.card ≤ choices) := by sorry