Theorem 1.4 — Marx's theorem under FPT ≠ W[1]
OpenSparseIncidenceHom.WidthComparison.Supplement.theorem_1_4p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexitysubmodular-widthw1-hardness
Let be a recursively enumerable class of hypergraphs.
- If has unbounded submodular width, then - is -hard (under FPT many-one reductions of promise problems).
- Consequently, assuming ,
The first clause is unconditional. The theorem replaces the Exponential Time Hypothesis in Marx's characterization of fixed-parameter tractable homomorphism problems by .
Formalization Note Classes, machines, FPT and are those of the definition item SparseIncidenceHom.WidthComparison.Supplement.Problems; promise W[1]-hardness is the published DetParamSVP.PromiseW1Hard.
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 (running time f(‖H_A‖)·N^{O(1)}) and W[1]-hardness → deterministic multi-tape machines of the published Cook–Levin cost model, correct on promise instances within f(k)·(|x|+1)^c steps (f computable), and published DetParamSVP.PromiseW1Hard; 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 and W[1]-hardness 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 1.4, p. 6 (restated p. 20). The first clause
is unconditional; the second assumes FPT ≠ W[1]. -/
theorem theorem_1_4 (𝓗 : HypergraphClass) (hre : IsREClass 𝓗) :
(¬ BoundedWidth 𝓗 (fun _ H => submodularWidth H) →
DetParamSVP.PromiseW1Hard (pHomHyp 𝓗)) ∧
(FPTneW1 →
(InFPT (pHomHyp 𝓗) ↔ BoundedWidth 𝓗 (fun _ H => submodularWidth H))) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 6, Theorem 1.4 (restated p. 20); proof p. 21 (Lemmas 6.1, 6.2 and [Mar13])