Panagiotis Aivasiliotis, Hubie Chen, Andreas Göbel, Matthias Lanzinger, Marc Roth, Markus Schneider
The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the contexts of descriptive complexity, logics, graph neural networks, and the theory of homomorphism indistinguishabily. Notably, two graphs are indistinguishable by the $k$-dimensional WL algorithm if and only if they are indistinguishable by homomorphism-counts from graphs of treewidth at most $k$. An intrinsic question is to find a natural version of the WL algorithm for relational structures of higher arity admitting an equivalent characterisation via homomorphism indistinguishability along bounded generalised hypertree width (GHW). Scheidt and Schweikardt solved this for $k=1$ by defining the RCR algorithm and showing indistinguishability from $α$-acyclic structures. In this work, we resolve this for all $k\ge1$: we develop a $k$-dimensional version of RCR ($k$-RCR for short) and show that two structures $\mathcal A$ and $\mathcal B$ are indistinguishable by $k$-RCR if and only if they have the same number of homomorphisms from all structures $\mathcal C$ of generalised hypertreewidth at most $k$. Furthermore, we show that on a structure $\mathcal A$ over a fixed signature, with $\mathsf{ghw}(\mathcal{A})\leq k$, $k$-RCR runs in $O(\|\mathcal A\|^k\cdot\log(\|\mathcal A\|))$, where $\|\mathcal A\|$ is the number of all tuples that appear in the relations of $\mathcal A$.
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]$.