Summary
This paper studies a type of mathematical problem called homomorphism problems that involve mapping one network-like structure into another. The authors find that if certain complexity theory assumptions hold, then problems that can be solved efficiently when focusing on some small part of the input can also be solved efficiently on the whole input, for large classes of sparse and structured networks. Their approach allows for networks with very complex connections and uses recent advances in graph theory to characterize when efficient solutions are possible. This helps understand exactly which problem patterns allow efficient solving and counting of mappings.
What this means in practice
- •For database developers: Optimize query evaluation involving complex joins on large but sparse relational data by identifying tractable query patterns.
- •For constraint programming engineers: Design efficient solvers for constraint satisfaction problems with sparse or bounded independence structure by recognizing when tractability guarantees hold.
A theory result. No direct application yet.
Abstract
Assuming the Exponential Time Hypothesis (ETH), 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. In both cases, tractability is characterised by bounded fractional hypertree width. Grohe (JACM 2007) established the corresponding FPT-PTIME equivalence under bounded arity. Our result allows unbounded arity and covers important cases such as bounded-degree patterns and patterns whose incidence graphs exclude a fixed minor. Building on the recent fractional balanced-separator framework and rounding theorem of Korchemna et al. (FOCS 2024), we prove a near-linear bound on fractional hypertree width ($\mathsf{fhw}$) in terms of adaptive width ($\mathsf{adw}$). For every hypergraph $H$ with $\mathsf{adw}(H)\geq 2$, \[ \mathsf{fhw}(H)=O\bigl(λ(H)\mathsf{adw}(H)\log\mathsf{adw}(H)\bigr), \] where $λ(H)=\min\{μ(H),\max\{1,\logα(H)\}\}$, with $μ(H)$ denoting incidence degeneracy and $α(H)$ the independence number of the primal graph. As a further consequence, we obtain a corresponding FPT-PTIME collapse for exact homomorphism counting on every bounded-$λ$ class. More generally, for every recursively enumerable class of pattern hypergraphs, fixed-parameter tractability of the parameterised homomorphism problem implies quasipolynomial-time solvability of the corresponding unparameterised problem, assuming ETH.