Theorem 2 — deterministic QPTAS for maximum weight independent set
ProvedEdgeSublinearMWIS.Main.theorem_2Let be any hereditary class of finite simple undirected graphs with strongly edge-sublinear separators. There is one finite deterministic program for the entire class, with class-uniform , positive integer and a universal positive polynomial exponent . For every graph with vertices, arbitrary rational weights and rational , it returns an independent set satisfying
Here maximizes over all independent subsets including the empty set, and is the total binary length of the weight and accuracy encodings, including signs and prefixes. Every positive-denominator representation is accepted, including unreduced fractions. The finite program precedes every input and its time is the first actual halting step on a local binary Turing machine. It receives only adjacency, weights and accuracy. No class-membership oracle, separator, separator-finding algorithm, optimum or input-dependent advice is supplied.
This is the full weighted source target. Negative weights, empty graphs, singleton graphs and all-nonpositive vectors remain in the domain. The additive polynomial encoding work and the class-uniform quasipolynomial term are both preserved.
Differences from the source:
- encoding: arbitrary finite simple graphs → graphs labeled by Fin n and finite vertex masks; reason: every finite graph admits such a labeling; induced injections transport class membership
- encoding: rational weights and accuracy with binary length ell → arbitrary signed numerator and positive-denominator encodings, with sign and self-delimiting prefixes counted in ell; reason: every rational value and every such representation is included; normalization must be charged
- encoding: exp((epsilon inverse log n)^(O_C(1))) plus ell^(O(1)) → uniform K,d before all inputs, universal q before the class, and log_2(max(2,n)); reason: positive constants and padding express the source asymptotics; max handles its direct empty and singleton cases
- encoding: a deterministic algorithm without supplied separators → one ordinary finite bit machine, empty catalyst and first actual halting time; reason: no correctness, resource bound, optimizer or per-instance advice is assumed in the computational model
import Definitions.Def_EdgeSublinearMWIS_Main_Graphs import Definitions.Def_EdgeSublinearMWIS_Main_BitExecution open scoped BigOperators
namespace EdgeSublinearMWIS.Main
/-- Theorem 2, including its p.2 explanatory paragraph: arbitrary signed rational
weights, a single finite deterministic program, additive bit preprocessing, no oracle. -/
theorem theorem_2 :
∃ q : ℕ, 0 < q ∧ ∀ C : GraphClass, StronglyEdgeSublinear C →
∃ (M : CatalyticMatching.General.Machine) (K : ℝ) (d : ℕ), 0 < K ∧ 0 < d ∧
∀ (n : ℕ) (G : SimpleGraph (Fin n)) (w : Fin n → RationalCode)
(ε : RationalCode), C n G → 0 < ε.value → ε.value < 1 →
∃ (I : Finset (Fin n)) (s : ℕ),
BitHalts M (weightedInput G w ε) (mask I) s ∧
G.IsIndepSet (I : Set (Fin n)) ∧
(1 - (ε.value : ℝ)) * weightedAlpha G (fun v => (w v).value) ≤
∑ v ∈ I, ((w v).value : ℝ) ∧
(s : ℝ) ≤ K * Real.exp
(K * (((ε.value : ℝ))⁻¹ * logTwo (max 2 n)) ^ d) +
K * ((rationalData w ε).length + 1 : ℝ) ^ q := by sorry
end EdgeSublinearMWIS.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.