@proceedings{Kutner_D-2023_163720,
title = {Temporal Reachability Dominating Sets: Contagion in Temporal Graphs},
author = {Kutner, D. and Larios-Jones, L.},
month = {dec},
year = {2023},
abstract = {SARS-CoV-2 was independently introduced to the UK at least 1300 times by June 2020. Given a population with dynamic pairwise connections, we ask if the entire population could be (indirectly) infected by a small group of k initially infected individuals. We formalise this problem as the Temporal Reachability Dominating Set (TaRDiS) problem on temporal graphs. We provide positive and negative parameterized complexity results in four different parameters: the number k of initially infected, the lifetime τ of the graph, the number of locally earliest edges in the graph, and the treewidth of the footprint graph G↓. We additionally introduce and study the MaxMinTaRDiS problem, which can be naturally expressed as scheduling connections between individuals so that a population needs to be infected by at least k individuals to become fully infected. Interestingly, we find a restriction of this problem to correspond exactly to the well-studied Distance-3 Independent Set problem on static graphs.},
pages = {101-116},
journal = {Algorithmics of Wireless Networks},
publisher = {Springer Nature},
url = {https://publichealthscotland.scot/id/163720},
}
