Theorem 1.2 — FPT iff PTIME iff bounded fhw for r.e. classes of bounded incidence degeneracy or primal independence
OpenSparseIncidenceHom.WidthComparison.Supplement.theorem_1_2Let be a recursively enumerable hypergraph class such that the incidence degeneracy is bounded over , or the primal independence number is bounded over . Assume . Then
and these conditions hold exactly when has bounded fractional hypertree width, i.e. .
Here asks, for finite relational structures over the same signature with , whether , and - is its parameterization by . Both are promise problems: inputs with carry no requirement.
This theorem says that on these sparse classes extra running time depending on the pattern gives no advantage, and that fractional hypertree width is the exact tractability boundary.
Formalization Note Classes, machines, FPT, PTIME and are those of the definition item SparseIncidenceHom.WidthComparison.Supplement.Problems.
Differences from the source:
- generalization: every member of a hypergraph class is nonempty and connected (p. 7: "We assume input hypergraphs are nonempty and connected") → classes may contain empty or disconnected hypergraphs (every H_A of a structure, published FiniteHypergraph without InputHypergraph); reason: on a class of nonempty connected hypergraphs the Lean statement is the source's; widths, incidence degeneracy, boundedness of α and Hom decompose over connected components, and the empty hypergraph has every width 0
- encoding: a recursively enumerable hypergraph class with membership up to isomorphism → a set of hypergraph codes (n, edge lists) that is an r.e. predicate, H belonging to it when some code describes H up to isomorphism; reason: Lean convention for classes; the same classes
- encoding: FPT and PTIME (running time f(‖H_A‖)·N^{O(1)}, resp. polynomial) → deterministic multi-tape machines of the published Cook–Levin cost model, correct on promise instances within f(k)·(|x|+1)^c (f computable), resp. c·(|x|+1)^d steps; reason: standard machine model
- encoding: ‖H_A‖, the length of the list of edges as vertex lists → Σ_e (|e|+1); reason: each is bounded by a computable function of the other, so FPT membership is unchanged
- encoding: ‖A‖, explicit tuple lists → a self-delimiting unary encoding of signature, domain size and tuple lists; reason: polynomially related to any standard encoding, so PTIME and FPT are unchanged
- encoding: FPT ≠ W[1] → some problem FPT-reducible to p-Clique (published InW1) is not in FPT; reason: equivalent, since FPT ⊆ W[1]
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Problems
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Theorem 1.2, p. 5. -/
theorem theorem_1_2 (𝓗 : HypergraphClass) (hre : IsREClass 𝓗)
(hsparse : BoundedDegeneracyOrIndependence 𝓗) (hW : FPTneW1) :
(InFPT (pHomHyp 𝓗) ↔ InPTIME (homHyp 𝓗)) ∧
(InFPT (pHomHyp 𝓗) ↔ BoundedWidth 𝓗 (fun _ H => fractionalHypertreeWidth H)) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement