2023/06/12 by David C. Kutner, Kutner, David C., Laura Larios-Jones +1 · 1 citation
Computer Science · Social Sciences · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Human Mobility and Location-Based Analysis #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.2306.06999
openalex publication_date 2023/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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_\downarrow. 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 Σ2P-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.