RAM program: exact maximum-weight independent set for tree-width in operations
OpenWilliamsonShmoys.treewidth_mwis_ram_solverExact 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 and constants with the following property. Let and be integers, let be an adjacency table, and let be an arbitrary real weight vector. Let be the simple graph on in which distinct vertices are adjacent if and only if or , and write . Start on the standard input layout: natural cells and hold and , the next natural cells hold row by row, real cells hold , and every other cell holds . If has tree-width at most , then after some number of operations with
the program counter of points at a halt instruction, and at that moment:
- each of the output cells (natural cells ) contains or ;
- the set of vertices whose output cell contains is an independent set of ;
- has maximum weight among all independent sets of :
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 , with running time . The program is given the width bound (in the cell that holds the accuracy parameter in the band problem) but no tree decomposition. With 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 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.
import Definitions.Def_WilliamsonShmoys_PlanarIndependentSetRAM import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE set_option autoImplicit false open scoped BigOperators
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