Publications (41)
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.…
Cops and Robbers on Multi-Layer Graphs
Jessica Enright, Kitty Meeks, William Pettersson +1
We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuit…
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…
The parameterised complexity of counting even and odd induced subgraphs
Mark Jerrum, Kitty Meeks
We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting t…
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…
Reachability in temporal graphs under perturbation
Jessica Enright, Laura Larios-Jones, Kitty Meeks +1
Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors i…