Theorem 4.1 — bounded fhw, bounded subw, FPT and PTIME coincide on sparse r.e. hypergraph classes
OpenSparseIncidenceHom.WidthComparison.Supplement.theorem_4_1fractional-hypertree-widthhomomorphismsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexitysubmodular-width
Let be a recursively enumerable hypergraph class of bounded incidence degeneracy or bounded independence number. Assuming , the following are equivalent.
- has bounded fractional hypertree width.
- has bounded submodular width.
- -.
- .
Bounded width means ; bounded incidence degeneracy or independence number means or . The theorem implies Theorem 1.2.
Formalization Note The equivalence is stated with Mathlib's List.TFAE. 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 → 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]
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Problems
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Theorem 4.1, p. 15. -/
theorem theorem_4_1 (𝓗 : HypergraphClass) (hre : IsREClass 𝓗)
(hsparse : BoundedDegeneracyOrIndependence 𝓗) (hW : FPTneW1) :
List.TFAE
[BoundedWidth 𝓗 (fun _ H => fractionalHypertreeWidth H),
BoundedWidth 𝓗 (fun _ H => submodularWidth H),
InFPT (pHomHyp 𝓗),
InPTIME (homHyp 𝓗)] := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 15, Theorem 4.1; proof p. 15