2 citations · 4 across the 13 of their papers we have counts for
21 papers
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 …
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…
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…
Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process
Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz
The multi-type Moran process is an evolutionary process on a connected graph in which each vertex has one of types and, in each step, a vertex is chosen to reproduce it…
Parameterised and Fine-grained Subgraph Counting, modulo
Leslie Ann Goldberg, Marc Roth
Given a class of graphs , the problem is defined as follows. The input is a graph together with an arbitrary graph…
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…