RAM reduction: an exact bounded-tree-width independent-set program yields the best-of- shifted band solver
OpenWilliamsonShmoys.baker_shifting_ram_reductionBaker's shifting step, stated as a reduction between programs for the unit-cost real RAM of WilliamsonShmoys_PlanarIndependentSetRAM.
For an adjacency table on let be its graph (distinct adjacent if and only if or ), let be the BFS level of (bakerLevel: the distance from the smallest vertex of its connected component), and write for a real weight vector . The standard input layout with parameter puts in natural cells , the table in the next natural cells, in real cells , and everywhere else; the output bitmap is natural cells .
Suppose is a program and are constants such that solves maximum-weight independent set exactly on graphs of tree-width at most : for every , every table whose graph has tree-width at most and every , the program started on the standard input layout with parameter reaches a halt instruction after operations with , its output bitmap consists of cells, and it describes an independent set of with for every independent set of .
Then there are a program and constants such that for every , every , every table and every the following holds. If for each the graph obtained from by deleting the vertices with has tree-width at most , then , started on the standard input layout with parameter , reaches a halt instruction after operations with
its output bitmap consists of cells and describes an independent set of , and
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 graphs , and return the heaviest of the 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 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 , not which memory cells it uses.
import Definitions.Def_WilliamsonShmoys_PlanarIndependentSetRAM import Definitions.Def_WilliamsonShmoys_BakerLevel import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE set_option autoImplicit false open scoped BigOperators
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