Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bounded-treewidth finite DP with a small decomposition and linear plan size

Proved
StableMSR.Recovery.TreeDP.bounded_treewidth_dp

by lreyzin · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

For every finite graph GGG on nnn vertices of treewidth at most www, there exists a width-www tree decomposition with at most n+1n+1n+1 bags, chosen before its local data. For every matching local allocation with at most BBB represented choices per bag, there is a coherent local binary DP plan with at most 2n+12n+12n+1 nodes preserving the original validity, representability, total count, and total objective. At every feasible count at most a cap KKK, the retained table contains a represented global optimum. The root table has at most B(K+1)B(K+1)B(K+1) entries and the total table and raw candidate volumes satisfy

T≤(2n+1)B(K+1),R≤(2n+1)B3(K+1)2.T\le(2n+1)B(K+1),\qquad R\le(2n+1)B^3(K+1)^2.T≤(2n+1)B(K+1),R≤(2n+1)B3(K+1)2.

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.

Preamble
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
Formal statement
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
Source
Composition of the proved Prove2Me results finite_decomposition_search (d4f2a14a-b18f-44f7-966a-d1411797cf17) and decomposition_dp_exact_optimum (c235355c-a873-47eb-8aaa-cd861894915e), supporting the Exact Sum-of-Radii Clustering under Any Constant Stability mission.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me