University of Glasgow
Parameterised complexity of spreading problems on temporal graphs
Abstract
dc:description.abstractSpreading 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 × 1Rights
- Language dc:language
- en
Identifiers
dc:identifier.*- DOI dc:identifier.doi
- https://doi.org/10.5525/gla.thesis.84865