Temporal Reachability Dominating Sets: Contagion in Temporal Graphs

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.

Rights

This content is not covered by the Open Government Licence. Please see source record or item for information on rights and permissions.

Cite as

Downloadable citations

Identifiers

Repository URI

https://eprints.gla.ac.uk/308905/