Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

RAM reduction: an exact bounded-tree-width independent-set program yields the best-of-kkk shifted band solver

Open
WilliamsonShmoys.baker_shifting_ram_reduction

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

approximation-algorithmsindependent-settreewidth

Baker's shifting step, stated as a reduction between programs for the unit-cost real RAM of WilliamsonShmoys_PlanarIndependentSetRAM.

For an adjacency table EEE on {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} let GGG be its graph (distinct u,vu,vu,v 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), let ℓ(v)\ell(v)ℓ(v) be the BFS level of vvv (bakerLevel: the distance from the smallest vertex of its connected component), and write ω(X)=∑v∈Xω(v)\omega(X)=\sum_{v\in X}\omega(v)ω(X)=∑v∈X​ω(v) for a real weight vector ω\omegaω. The standard input layout with parameter ppp puts n,pn,pn,p in natural cells 0,10,10,1, the table in the next n2n^2n2 natural cells, ω\omegaω in real cells 0,…,n−10,\dots,n-10,…,n−1, and 000 everywhere else; the output bitmap is natural cells 2+n2,…,1+n2+n2+n^2,\dots,1+n^2+n2+n2,…,1+n2+n.

Suppose PPP is a program and C0,d0>0C_0,d_0>0C0​,d0​>0 are constants such that PPP solves maximum-weight independent set exactly on graphs of tree-width at most www: for every w,nw,nw,n, every table EEE whose graph GGG has tree-width at most www and every ω\omegaω, the program PPP started on the standard input layout with parameter www reaches a halt instruction after ttt operations with t+1≤C0 2d0w(n+1)2t+1\le C_0\,2^{d_0w}(n+1)^2t+1≤C0​2d0​w(n+1)2, its output bitmap consists of 0/10/10/1 cells, and it describes an independent set AAA of GGG with ω(S)≤ω(A)\omega(S)\le\omega(A)ω(S)≤ω(A) for every independent set SSS of GGG.

Then there are a program QQQ and constants C,d>0C,d>0C,d>0 such that for every k≥1k\ge1k≥1, every nnn, every table EEE and every ω\omegaω the following holds. If for each 0≤j<k0\le j<k0≤j<k the graph GjG_jGj​ obtained from GGG by deleting the vertices vvv with ℓ(v)≡j(modk)\ell(v)\equiv j\pmod kℓ(v)≡j(modk) has tree-width at most 3k3k3k, then QQQ, started on the standard input layout with parameter kkk, reaches a halt instruction after ttt operations with

t+1≤C 2dk (n+1)2,t+1\le C\,2^{dk}\,(n+1)^2,t+1≤C2dk(n+1)2,

its output bitmap consists of 0/10/10/1 cells and describes an independent set AAA of GGG, and

ω(S)≤ω(A)for all j<k and all independent sets S of G with ℓ(v)≢j(modk) for every v∈S.\omega(S)\le\omega(A)\qquad\text{for all } j<k \text{ and all independent sets } S \text{ of } G \text{ with } \ell(v)\not\equiv j \pmod k \text{ for every } v\in S.ω(S)≤ω(A)for all j<k and all independent sets S of G with ℓ(v)≡j(modk) for every v∈S.

This isolates the shifting part of the algorithmic half of Baker's PTAS (Williamson–Shmoys, Section 10.2, proof of Theorem 10.11): compute the BFS levels, solve maximum-weight independent set exactly on each of the kkk graphs GjG_jGj​, and return the heaviest of the kkk solutions. Combined with an exact bounded-tree-width solver such as WilliamsonShmoys.treewidth_mwis_ram_solver, it gives WilliamsonShmoys.band_treewidth_ram_solver.

Formalization Note The hypothesis on PPP is the body of WilliamsonShmoys.treewidth_mwis_ram_solver with its existentially quantified program and constants turned into parameters, and the conclusion is verbatim the statement of WilliamsonShmoys.band_treewidth_ram_solver. The hypothesis constrains only the input-output behaviour and running time of PPP, not which memory cells it uses.

Preamble
import Definitions.Def_WilliamsonShmoys_PlanarIndependentSetRAM
import Definitions.Def_WilliamsonShmoys_BakerLevel
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE

set_option autoImplicit false
open scoped BigOperators
Formal statement
namespace WilliamsonShmoys
theorem baker_shifting_ram_reduction
    (solver : List PlanarRAMInstruction) (C₀ d₀ : ℕ) (hC₀ : 0 < C₀) (hd₀ : 0 < d₀)
    (hsolver : ∀ (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 solver (planarRAMInput n w edge weight) t
        solver[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) :
    ∃ (program : List PlanarRAMInstruction) (C d : ℕ),
      0 < C ∧ 0 < d ∧
      ∀ (k : ℕ), 0 < k →
      ∀ (n : ℕ) (edge : Fin n → Fin n → Bool) (weight : Fin n → ℝ),
        let G := SimpleGraph.fromRel (fun u v => edge u v = true)
        (∀ j < k, RobertsonSeymour1986.GM5.TreewidthLE
          (G.induce {v : Fin n | bakerLevel G v % k ≠ j}) (3 * k)) →
        ∃ t : ℕ, t + 1 ≤ C * 2 ^ (d * k) * (n + 1) ^ 2 ∧
          let result := planarRAMRun program (planarRAMInput n k 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)) ∧
          ∀ j < k, ∀ S : Finset (Fin n), G.IsIndepSet (S : Set (Fin n)) →
            (∀ v ∈ S, bakerLevel G v % k ≠ j) →
            ∑ 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: compute the BFS levels, for each of the k shifts solve the tree-width-bounded instance exactly, and output the best of the k solutions. Shifting technique: B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. ACM 41(1) (1994) 153-180, https://doi.org/10.1145/174644.174650.

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