Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

RAM program: exact maximum-weight independent set for tree-width ≤w\le w≤w in C 2dw(n+1)2C\,2^{dw}(n+1)^2C2dw(n+1)2 operations

Open
WilliamsonShmoys.treewidth_mwis_ram_solver

by amirh · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsindependent-settreewidth

Exact maximum-weight independent set on graphs of bounded tree-width, computed by one fixed program for the unit-cost real RAM of WilliamsonShmoys_PlanarIndependentSetRAM.

There are a finite program PPP and constants C,d>0C,d>0C,d>0 with the following property. Let w≥0w\ge 0w≥0 and n≥0n\ge 0n≥0 be integers, let E:{0,…,n−1}2→{0,1}E:\{0,\dots,n-1\}^2\to\{0,1\}E:{0,…,n−1}2→{0,1} be an adjacency table, and let ω:{0,…,n−1}→R\omega:\{0,\dots,n-1\}\to\mathbb Rω:{0,…,n−1}→R be an arbitrary real weight vector. Let GGG be the simple graph on {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} in which distinct vertices u,vu,vu,v are adjacent if and only if E(u,v)=1E(u,v)=1E(u,v)=1 or E(v,u)=1E(v,u)=1E(v,u)=1, and write ω(X)=∑v∈Xω(v)\omega(X)=\sum_{v\in X}\omega(v)ω(X)=∑v∈X​ω(v). Start PPP on the standard input layout: natural cells 000 and 111 hold nnn and www, the next n2n^2n2 natural cells hold EEE row by row, real cells 0,…,n−10,\dots,n-10,…,n−1 hold ω\omegaω, and every other cell holds 000. If GGG has tree-width at most www, then after some number ttt of operations with

t+1≤C 2dw (n+1)2t+1\le C\,2^{dw}\,(n+1)^2t+1≤C2dw(n+1)2

the program counter of PPP points at a halt instruction, and at that moment:

  1. each of the nnn output cells (natural cells 2+n2,…,1+n2+n2+n^2,\dots,1+n^2+n2+n2,…,1+n2+n) contains 000 or 111;
  2. the set AAA of vertices whose output cell contains 111 is an independent set of GGG;
  3. AAA has maximum weight among all independent sets of GGG:
ω(S)≤ω(A)for every independent set S of G.\omega(S)\le\omega(A)\qquad\text{for every independent set } S \text{ of } G.ω(S)≤ω(A)for every independent set S of G.

This is the exact subproblem that the algorithmic half of Baker's PTAS solves once per shift (Williamson–Shmoys, Section 10.2, proof of Theorem 10.11): maximum-weight independent set on a graph of tree-width O(k)O(k)O(k), with running time 2O(k)n22^{O(k)}n^22O(k)n2. The program is given the width bound www (in the cell that holds the accuracy parameter kkk in the band problem) but no tree decomposition. With w=3kw=3kw=3k it supplies the per-shift solver for WilliamsonShmoys.band_treewidth_ram_solver, and it is a reusable statement of the classical fact that weighted independent set is solvable in time single-exponential in the tree-width.

Formalization Note Tree-width at most www is RobertsonSeymour1986.GM5.TreewidthLE. The graph is SimpleGraph.fromRel of the table, so the table need not be symmetric and its diagonal is ignored. Weights may be negative, in which case the empty set can be optimal. The input layout, the output bitmap, the step function and the halting convention are exactly those of WilliamsonShmoys.band_treewidth_ram_solver.

Preamble
import Definitions.Def_WilliamsonShmoys_PlanarIndependentSetRAM
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE

set_option autoImplicit false
open scoped BigOperators
Formal statement
namespace WilliamsonShmoys
theorem treewidth_mwis_ram_solver :
    ∃ (program : List PlanarRAMInstruction) (C d : ℕ),
      0 < C ∧ 0 < d ∧
      ∀ (w n : ℕ) (edge : Fin n → Fin n → Bool) (weight : Fin n → ℝ),
        let G := SimpleGraph.fromRel (fun u v => edge u v = true)
        RobertsonSeymour1986.GM5.TreewidthLE G w →
        ∃ t : ℕ, t + 1 ≤ C * 2 ^ (d * w) * (n + 1) ^ 2 ∧
          let result := planarRAMRun program (planarRAMInput n w edge weight) t
          program[result.pc]? = some PlanarRAMInstruction.halt ∧
          (∀ i : Fin n, result.natMem (2 + n * n + i.val) ≤ 1) ∧
          G.IsIndepSet (planarRAMOutput n result : Set (Fin n)) ∧
          ∀ S : Finset (Fin n), G.IsIndepSet (S : Set (Fin n)) →
            ∑ i ∈ S, weight i ≤ ∑ i ∈ planarRAMOutput n result, weight i := by sorry
end WilliamsonShmoys
Source
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, author electronic manuscript, Section 10.2, proof of Theorem 10.11, pp. 270-272, https://doi.org/10.1017/CBO9780511921735: for each shift the algorithm solves maximum-weight independent set exactly on a graph of tree-width O(k) by finding a tree decomposition and running dynamic programming, O(2^{O(k)} n^2) time. Standard algorithms for the two steps: a tree decomposition of width at most 4w+4 in time 2^{O(w)} n^2 (N. Robertson and P. D. Seymour, Graph Minors XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995) 65-110, https://doi.org/10.1006/jctb.1995.1006; textbook presentation in M. Cygan et al., Parameterized Algorithms, Springer 2015, Section 7.6), and the weighted independent set dynamic program over a tree decomposition in time 2^{O(w)} n (Cygan et al., Section 7.3.1).

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