Back to search

University of Glasgow

Parameterised complexity of spreading problems on temporal graphs

Abstract

dc:description.abstract

Spreading problems are a class of decision problems on graphs that can be used to model the behaviour of a spread of a contagion over a network. Real world networks are often dynamic in nature, with the connections between the members of the network changing over time. Take for example the contact network of a population of people: individuals may come into contact for a period of time, and then move apart and contact other individuals. Graphs do not model this dynamic behaviour, and as such in this thesis we consider spreading problems on temporal graphs, which overcome this shortfall by augmenting a graph with temporal information. In particular we consider the problems of Temporal Firefighter and Temporal Graph Burning, extensions of the Firefighter and Graph Burning problems to temporal graphs. Temporal Firefighter asks how to best prevent the vertices of a temporal graph from “burning” when a fire is spreading over the graph, and Temporal Graph Burning asks how best to burn the vertices of a temporal graph to spread a fire as fast as possible. Both of these problems are NPcomplete, and unlikely to yield efficient algorithms in general. Parameterised complexity theory provides tools for obtaining efficient algorithms for NP-complete problems, and in this thesis we consider various parameters for temporal graphs. We find that both Temporal Firefighter and Temporal Graph Burning are in FPT when parameterised by vertex-interval-membership-width and by temporal neighbourhood diversity. Furthermore, we prove a meta-theorem for showing that a temporal graph problem is in FPT when parameterised by vertex-interval-membership-width. Overall we demonstrate the usefulness of temporal graph parameters, suggesting future work in applying these to more problems on temporal graphs.

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hand, Samuel

Subjects

dc:subject × 1

Rights

Language dc:language
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hand, Samuel. Parameterised complexity of spreading problems on temporal graphs. PhD thesis, University of Glasgow, 2025. https://doi.org/10.5525/gla.thesis.84865