3 papers
cs.CC2026
The Parameterised Complexity of Temporal Motif Counting, and a Lovász-Style Isomorphism Theorem
Jayakrishnan Madathil, Kitty Meeks, Marc Roth
We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern …
cs.CC2026
The Fine-Grained Complexity of Counting Hypergraph Motifs
Madhumitha Krishnakumar, Marc Roth
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 p…
cs.CC2026
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…