Graph encoding and polynomial Max-Cut approximation
DefinitionIntervalMaxCutEPTAS_Scheme_Supplement_HardnessGraph input consists of a self-delimiting binary vertex count followed by the upper-triangular adjacency bits in lexicographic order. A cut output is exactly the membership bits in input vertex order. A polynomial approximator for a class is a single finite-alphabet Turing-machine computation , polynomial in binary input length, such that
The machine and its polynomial are fixed before every input. No class certificate or optimum is supplied. The polynomial-time transducer, and the actual language classes and , are the published standard TM2 definitions in PvsNP: finite alphabets and machine control, polynomial decision time, and polynomial-length witnesses checked in polynomial time. The chordal and restricted classes contain every graph of the respective source class, including edgeless graphs. This is the approximation notion used in the hardness theorem, not an opaque hardness premise.
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Graph
import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_Classes
set_option autoImplicit false
namespace IntervalMaxCutEPTAS.Scheme.Supplement
/-- Self-delimiting binary natural number: unary bit length, zero, then low-first binary bits. -/
def naturalCode (n : ℕ) : List Bool :=
List.replicate (Nat.bits n).length true ++ [false] ++ Nat.bits n
/-- n followed by the upper triangle in lexicographic order, no advice or optimum. -/
def graphCode {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] : List Bool :=
naturalCode n ++ (List.finRange n).flatMap (fun u =>
((List.finRange n).filter (fun v => u < v)).map (fun v => decide (G.Adj u v)))
/-- Exactly n bits, in input vertex order. -/
def cutCode {n : ℕ} (S : Finset (Fin n)) : List Bool := List.ofFn (fun v => decide (v ∈ S))
abbrev GraphClass := (n : ℕ) → SimpleGraph (Fin n) → Prop
def chordalClass : GraphClass := fun _ G => GavrilSubtree.Chordal.IsChordal G
def restrictedClass : GraphClass := fun _ G => SplitPlusTwo G
/-- One finite-alphabet machine for all graph strings, with polynomial running time in their
binary length (the published TM2 definition), and a fixed n-bit output. Invalid strings may be
rejected by any total polynomial-time extension. The promise is solely membership in C. -/
def PolynomialApproximation (β : ℝ) (C : GraphClass) : Prop :=
∃ f : List Bool → List Bool, PvsNP.PolyTimeComputable f ∧
∀ (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj], C n G →
∃ S : Finset (Fin n), f (graphCode G) = cutCode S ∧
β * (mc G : ℝ) ≤ (cutCount G S : ℝ)
end IntervalMaxCutEPTAS.Scheme.Supplement