Temporal Reachability Dominating Sets: Contagion in temporal graphs
David C. Kutner, Laura Larios-Jones · Journal of Computer and System Sciences · 2025
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, where the aim is to schedule connections between individuals so that at least k individuals must be infected for the entire population to become fully infected. We classify three variants of the problem: Strict, Nonstrict, and Happy. We show these to be coNP-complete, NP-hard, and ΣP2-complete, respectively. Interestingly, we obtain hardness of the Nonstrict variant by showing that a natural restriction is exactly the well-studied Distance-3 Independent Set problem on static graphs.