Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An exact binary DP plan for every finite tree decomposition

Proved
StableMSR.Recovery.TreeDP.binary_plan_from_decomposition

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

Let a finite tree decomposition have NNN 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 WWW variables and at most BBB assignment choices. There is a coherent binary plan PPP such that

∣P∣=2N−1.|P|=2N-1.∣P∣=2N−1.

Its root bag and choices are unchanged, it covers every variable, and every record still has at most WWW variables and BBB 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.

Preamble
import Definitions.Def_StableMSR_BinaryTreeDP_Plan
import Definitions.Def_RobertsonSeymour1986_GM5_IsTreeDecomposition
import Mathlib.Data.Finset.Card
open StableMSR.Recovery.TreeDP
open scoped BigOperators
Formal statement
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
Source
Prove2Me mission Exact Sum-of-Radii Clustering under Any Constant Stability; finite decomposition-to-DP construction, recursive rooted-component expansion.

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