A graph records pairs of objects that cannot be chosen together. An independent set is a choice with no conflicting pair. When each vertex has a nonnegative weight, maximum weighted independent set asks for a conflict-free set with the greatest total weight. This model occurs when choices have values and pairwise incompatibilities. On general graphs the optimization problem is difficult; the planar restriction gives a concrete geometric promise under which approximation is possible. Williamson and Shmoys state a polynomial-time approximation scheme for planar maximum independent set as Theorem 10.11 of The Design of Approximation Algorithms, in the author electronic manuscript at PDF/manuscript page 271.
The instance has vertices labeled by Fin n, an adjacency table edge : Fin n → Fin n → Bool, and a real weight weight i for each vertex. SimpleGraph.fromRel turns the table into an undirected simple graph G. The theorem requires every weight to be nonnegative. A finite set S is feasible when G.IsIndepSet (S : Set (Fin n)) holds. Its value is ∑ i ∈ S, weight i.
Planarity is expressed by HasPlanarDrawing G: vertices are placed at distinct points of the real plane, and every edge is represented by a continuous simple arc. An arc has no vertex in its interior, and distinct edges can meet only at endpoints. This is a concrete local drawing convention for the planar graph promise. The drawing witnesses the hypothesis; it is not passed as part of the algorithm's input.
The computational model is a fixed finite unit-cost RAM program. Its input includes the vertex count, an integer accuracy parameter, a complete adjacency table, and the real weights in named memory cells. Its instructions include natural-number and real addition and subtraction, exact comparisons, random-access loads and stores, branches, jumps, and halt. The machine starts with the instance preloaded and produces a bitmap after the adjacency table. This precise instruction set is a formalization convention: the book states an arithmetic-operation running time but does not specify a machine language.
For every real , let . The goal asserts that a single finite program and fixed positive natural constants work for every planar instance and every vector of nonnegative real weights. The program must halt after a number of operations satisfying
Its bitmap must represent an independent set , and for every independent set ,
Comparison with every feasible includes an optimal solution. The same program and constants precede all accuracy and instance quantifiers. The form includes the empty graph without imposing zero running time. The result corresponds to the bound in Theorem 10.11; the formal statement makes the constants and accuracy parameter explicit.
The result supplies an accuracy-time tradeoff for planar weighted independent set: any fixed positive accuracy has a quadratic dependence on graph size in this operation model, while the accuracy dependence is exponential. It separates the planar setting from the general graph problem. The finite instruction set and input layout make the computational claim inspectable, including what information the program receives and what counts as an operation.
The cited result is known in the textbook. This mission asks for a Lean proof of the packaged statement; the theorem currently has sorry, and no machine construction or correctness proof is claimed. The original local statement was compiled and source reviewed before packaging. That prior result establishes statement validity in its source workspace, while the upload payload is checked separately.
A high-quality independent set in each planar region does not immediately give a high-quality global set: edges across regions can create conflicts, and discarding boundary vertices can lose weight. A proof must coordinate the approximation inequality with a uniform operation bound for one program across all graph sizes, accuracies, and real weight vectors. It must also show the computed bitmap is always independent and that execution reaches an explicit halt instruction within the bound. These requirements rule out treating an optimizer, an embedding, or a best solution as preloaded input.
The goal uses finite labeled graphs, nonnegative arbitrary real weights, exact real arithmetic, and the concrete drawing predicate above. It does not claim a bit-complexity bound for encoded reals. The RAM starts from a complete adjacency table and weight vector, with no supplied drawing or optimum. Its step function is deterministic; an invalid program counter is stuck, so the theorem explicitly requires a halt instruction. Outputs are bits in designated natural memory cells and are checked for validity before their weighted value is compared.
The packaged definitions are the drawing predicate, instruction type, state, transition, iteration, input layout, and output decoder. They contain no proof axioms or optimization oracle. The rational-input polynomial bit-time fragment in the source workspace is a separate statement and is outside this goal. A complete contribution would construct the finite program and prove its running time and approximation guarantee in the specified model.
namespace WilliamsonShmoys
theorem planar_independent_set_sharp_real_ptas :
∃ (program : List PlanarRAMInstruction) (C d : ℕ),
0 < C ∧ 0 < d ∧
∀ (ε : ℝ), 0 < ε →
∀ (n : ℕ) (edge : Fin n → Fin n → Bool) (weight : Fin n → ℝ),
let G := SimpleGraph.fromRel (fun u v => edge u v = true)
let k := max 1 ⌈ε⁻¹⌉₊
HasPlanarDrawing G → (∀ i, 0 ≤ weight i) →
∃ 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)) ∧
∀ S : Finset (Fin n), G.IsIndepSet (S : Set (Fin n)) →
(1 - ε) * (∑ i ∈ S, weight i) ≤
∑ i ∈ planarRAMOutput n result, weight i := by sorry
end WilliamsonShmoys
One finite RAM program and absolute positive constants give, for every positive real accuracy, planar graph size, adjacency table, and nonnegative real weight vector, a halting independent-set output of weight at least (1−ε) times every independent set, within C·2^(d·max(1,⌈1/ε⌉))·(n+1)² unit-cost operations.