The Parameterised Complexity of Counting Small Sub-Hypergraphs

Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given two hypergraphs H and G, compute the number of sub-hypergraphs of G isomorphic to H. Formally, for a family H of hypergraphs, let #Sub(H) be the restriction of the problem to H ∈ H; the induced variant #IndSub(H) is defined analogously. Our main contribution is a complete classification of the fixed-parameter tractability of these problems. Assuming the Exponential Time Hypothesis, we prove that #Sub(H) is fixed-parameter tractable if and only if H has bounded fractional co-independent edge-cover number, a novel graph parameter introduced in this work, and that #IndSub(H) is fixed-parameter tractable if and only if H has bounded fractional edge-cover number. Both results subsume pre-existing results for graphs as special cases. We also show that the fixed-parameter tractable cases of #Sub(H) and #IndSub(H) are unlikely to be in polynomial time, unless respectively #P = P and Graph Isomorphism ∈ P. This shows a separation with the special case of graphs, where the fixed-parameter tractable cases are known to actually be in polynomial time. From a technical standpoint, we turn to the hypergraph homomorphism basis and lift the complexity monotonicity principle due to Curticapean, Dell, and Marx [STOC 2017] from graphs to hypergraphs of unbounded rank. Moreover, we crucially rely on the integrality gap for fractional independent sets based on adaptive width due to Bressan, Lanzinger, and Roth [STOC 2023]. The heart of our proofs consists of a careful investigation of the adaptive width of the patterns that survive in the hypergraph homomorphism basis. We also consider a natural variant of sub-hypergraphs where edges are trimmed to the vertex subset; we show that, surprisingly, in this case complexity monotonicity fails.