Bounded-treewidth finite DP with a small decomposition and linear plan size
ProvedStableMSR.Recovery.TreeDP.bounded_treewidth_dpFor every finite graph on vertices of treewidth at most , there exists a width- tree decomposition with at most bags, chosen before its local data. For every matching local allocation with at most represented choices per bag, there is a coherent local binary DP plan with at most nodes preserving the original validity, representability, total count, and total objective. At every feasible count at most a cap , the retained table contains a represented global optimum. The root table has at most entries and the total table and raw candidate volumes satisfy
This result removes a supplied-decomposition hypothesis while retaining explicit locality, matching-bag, and bounded-choice hypotheses. It asserts semantic correctness and finite cardinality bounds, not an instruction-level running time or a construction of application-specific local data.
import Theorems.Thm_StableMSR_Recovery_DecompositionSearch_finite_decomposition_search import Theorems.Thm_StableMSR_Recovery_TreeDP_decomposition_dp_exact_optimum set_option autoImplicit false open scoped Classical BigOperators open RobertsonSeymour1986.GM5 StableMSR.Recovery.DecompositionSearch StableMSR.Recovery.TreeDP
theorem StableMSR.Recovery.TreeDP.bounded_treewidth_dp {V X : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (width : ℕ) (htw : TreewidthLE G width) :
∃ (T : Type) (ft : Fintype T) (dt : DecidableEq T)
(tree : SimpleGraph T) (bags : T → Finset V),
IsTreeDecomposition G tree bags ∧
(∀ t, (bags t).card ≤ width+1) ∧
@Fintype.card T ft ≤ Fintype.card V + 1 ∧
∀ (data : T → BagData V X) (choices : ℕ),
(∀ t, (data t).bag = bags t) →
(∀ t, (data t).Local) →
(∀ t, (data t).choices.card ≤ choices) →
∃ p : Plan V X,
p.Coherent ∧ p.Local ∧ p.nodes ≤ 2 * Fintype.card V + 1 ∧
p.AllData (fun d => d.bag.card ≤ width+1 ∧ d.choices.card ≤ choices) ∧
(∀ cap, (solve cap p).card ≤ choices * (cap+1)) ∧
(∀ cap,
p.tableVolume cap ≤ (2 * Fintype.card V + 1) * (choices * (cap+1)) ∧
p.rawCandidateVolume cap ≤
(2 * Fintype.card V + 1) * (choices ^ 3 * (cap+1) ^ 2)) ∧
(∀ (whole : V → X) (j : ℕ) (w : ℝ),
GlobalEvaluates p whole j w ↔
(∀ t, (data t).valid whole) ∧
(∀ t, ∃ a ∈ (data t).choices, AgreeOn (data t).bag whole a) ∧
(∑ t, (data t).count whole) = j ∧
(∑ t, (data t).weight whole) = w) ∧
∀ cap j, j ≤ cap →
(∃ whole : V → X, (∀ t, (data t).valid whole) ∧
(∀ t, ∃ a ∈ (data t).choices, AgreeOn (data t).bag whole a) ∧
(∑ t, (data t).count whole) = j) →
∃ e ∈ solve cap p, ∃ whole : V → X,
e.2.1 = j ∧ (∀ t, (data t).valid whole) ∧
(∀ t, ∃ a ∈ (data t).choices, AgreeOn (data t).bag whole a) ∧
(∑ t, (data t).count whole) = j ∧
(∑ t, (data t).weight whole) = e.2.2 ∧
∀ other : V → X, (∀ t, (data t).valid other) →
(∀ t, ∃ a ∈ (data t).choices, AgreeOn (data t).bag other a) →
(∑ t, (data t).count other) = j →
e.2.2 ≤ ∑ t, (data t).weight other := by sorry