27 citations · 100 across the 27 of their papers we have counts for
9 papers · 1 filter
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 …
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Holger Dell, John Lapinskas, Kitty Meeks
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle q…
Counting Subgraphs in Somewhere Dense Graphs
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks +1
We study the problems of counting copies and induced copies of a small pattern graph in a large host graph . Recent work fully classified the complexity of those problems ac…
Edge exploration of temporal graphs
Benjamin Merlin Bumpus, Kitty Meeks
We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast with the static case, it is NP-hard to determine whether a given temporal graph is tempora…
Assigning times to minimise reachability in temporal graphs
Jessica Enright, Kitty Meeks, Fiona Skerman
Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g.~the spread of disease or dissemination of informa…
The challenges of unbounded treewidth in parameterised subgraph counting problems
Kitty Meeks
Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area.…
Some hard families of parameterised counting problems
Mark Jerrum, Kitty Meeks
We consider parameterised subgraph-counting problems of the following form: given a graph G, how many k-tuples of its vertices have a given property? A number of such problems are…
The Parameterised Complexity of Counting Connected Subgraphs and Graph Motifs
Mark Jerrum, Kitty Meeks
We introduce a class of parameterised counting problems on graphs, p-#Induced Subgraph With Property(Φ), which generalises a number of problems which have previously been studied.…
The Parameterised Complexity of List Problems on Graphs of Bounded Treewidth
Kitty Meeks, Alexander Scott
We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List…