The Fine-Grained Complexity of Counting Hypergraph Motifs
2026-07-06 • Computational Complexity
Computational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors study the problem of counting specific small patterns called hypergraph motifs, which are defined by how three groups of items overlap. They focus on how difficult this counting is depending on the 'rank' (max size of groups) of the hypergraph. They show that all counting problems can be solved in roughly quadratic time relative to the number of groups, with a complexity depending on the rank. Moreover, they identify exactly when the counting can be sped up to near-linear time, which happens only for special patterns where one group fits entirely inside another. For other patterns, faster algorithms would contradict known complexity hypotheses.
hypergraphmotif countingVenn diagramfixed-parameter tractability (FPT)rankcomputational complexityTriangle HypothesisHyperclique Hypothesisexact counting algorithms
Authors
Madhumitha Krishnakumar, Marc Roth
Abstract
Introduced by Lee, Ko, and Shin (VLDB 2020), a hypergraph motif is a connected subhypergraph consisting of three hyperedges whose intersections satisfy a prescribed pattern. Such patterns are represented by Venn diagrams $\mathcal{V}\in\{0,1\}^7$, indicating which of the seven regions determined by three sets must be empty or non-empty. Lee et al. designed and implemented exact and approximate algorithms for counting, in a hypergraph $G$, the motifs specified by $\mathcal{V}$; their algorithms run in worst-case cubic time in the number of hyperedges of $G$. This cubic worst case can occur even for hypergraphs of bounded rank, and already for $2$-uniform hypergraphs, that is, for simple graphs. In this work, we give a complete fine-grained picture of the parameterised complexity of exact hypergraph motif counting with respect to the rank of the input hypergraph. We use $\tilde{O}$ to hide polylogarithmic factors in the input size. First, we show that every Venn diagram $\mathcal{V}$ admits an exact counting algorithm running in FPT-near-quadratic time, \[ f(\mathsf{rank}(G))\cdot \tilde{O}(|E(G)|^2), \] for some computable function $f$. Second, we precisely characterise when this can be improved to FPT-near-linear time. We prove that such an algorithm exists exactly for the degenerate Venn diagrams, namely those that force one of the three hyperedges to be fully contained in another. For all non-degenerate Venn diagrams, we show that no FPT-near-linear-time algorithm exists unless either the Triangle Hypothesis or the Hyperclique Hypothesis fails. Exact hypergraph motif counting is thus always fixed-parameter near-quadratic in the rank, and the degenerate Venn diagrams are precisely the cases admitting fixed-parameter near-linear time.