TY - CPAPER
AU - Kutner, David C.
AU - Larios-Jones, Laura
PY - 2023
DA - December
TI - Temporal Reachability Dominating Sets: Contagion in Temporal Graphs
EP - 116
AB - 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.
PB - Springer Nature
UR - https://eprints.gla.ac.uk/308905/
KW - Coronavirus (COVID-19)
KW - Digital health and technology
ER