Theorem 4.3 — core widths, FPT and PTIME coincide for r.e. structure classes of bounded incidence degeneracy
OpenSparseIncidenceHom.WidthComparison.Supplement.theorem_4_3coresfractional-hypertree-widthhomomorphismsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity
Let be a recursively enumerable class of finite relational structures with bounded incidence degeneracy. Assuming , the following are equivalent.
- has bounded fractional hypertree width.
- has bounded submodular width.
- -.
- .
Here - is parameterized by the pattern . Only bounded incidence degeneracy is assumed; the analogue under bounded primal independence is left open by the source.
Formalization Note The equivalence is stated with Mathlib's List.TFAE. The width of a structure is that of its hypergraph; the core conditions are required for every core map of every member.
Differences from the source:
- encoding: a recursively enumerable class of finite relational structures, A ∈ 𝒜 → a set of explicit structures that is an r.e. predicate, the promise A ∈ 𝒜 read up to isomorphism with a well-formed member, and every class condition read over the well-formed members (an ill-formed code denotes no structure); reason: Lean convention for classes; width and degeneracy conditions are isomorphism invariant
- 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: parameterization by the pattern A → parameter ‖A‖, its encoding length; reason: finitely many patterns have a given length, 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.3, p. 17. Only bounded incidence degeneracy
is assumed. -/
theorem theorem_4_3 (𝒜 : StructureClass) (hre : IsREStructureClass 𝒜)
(hdeg : BoundedStructureDegeneracy 𝒜) (hW : FPTneW1) :
List.TFAE
[CoreBoundedFhw 𝒜,
CoreBoundedSubw 𝒜,
InFPT (pHomStruct 𝒜),
InPTIME (homStruct 𝒜)] := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 17, Theorem 4.3; proof p. 17