arXiv:2609.21840 · v2

FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns

首次提交 2026-09-18 22:38

版本更新 2026-11-03 06:35

雷达观测 2026-11-04 23:40

摘要

We show that fixed-parameter tractability and polynomial-time solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded incidence degeneracy or bounded primal independence number, assuming $FPT \ne W[1]$. In both cases, tractability is characterised by bounded fractional hypertree width. This generalises a result of Grohe [JACM 2007] that established such an FPT-PTIME collapse for bounded-arity structures. We build on the fractional balanced-separator framework and rounding theorem of Korchemna, Lokshtanov, Saurabh, Surianarayanan, and Xue [FOCS 2024] to prove near-linear bounds on fractional hypertree width ($fhw$) in terms of adaptive width ($adw$). Namely, for every hypergraph $H$ $$fhw(H)=O(μ(H) adw(H)\log adw(H)), \quad fhw(H)=O(\log α(H) adw(H)\log adw(H))$$ where $μ(H)$ is the degeneracy of the incidence graph of $H$ and $α(H)$ the independence number of the primal graph of $H$. As a consequence, we obtain a corresponding FPT-PTIME collapse for exact homomorphism decision and counting on every class in which either incidence degeneracy or independence number is bounded. This includes a number of natural classes such as pattern hypergraphs of bounded degree. Additionally, we observe that for every r.e. class of pattern hypergraphs, fixed-parameter tractability of the parameterised homomorphism problem implies quasipolynomial-time solvability of the corresponding unparameterised problem, assuming $FPT \ne W[1]$. Our results rely on the characterisation of fixed-parameter tractable decision of homomorphism problems in terms of submodular width of Marx [JACM 2013], conditional on ETH. In light of the very recent potential refutation of the ETH, we show that the characterisation of Marx holds also under the assumption that $FPT \ne W[1]$.