Temporal Reachability Dominating Sets: contagion in temporal graphs

Kutner, David C.; Larios-Jones, Laura

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.

Citation

Kutner, D. C., & Larios-Jones, L. (2023, September). Temporal Reachability Dominating Sets: contagion in temporal graphs. Presented at ALGOWIN 2023: International Symposium on Algorithmics of Wireless Networks, Amsterdam, The Netherlands

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ALGOWIN 2023: International Symposium on Algorithmics of Wireless Networks
• Start Date: Sep 7, 2023
• End Date: Sep 8, 2023
• Acceptance Date: Aug 1, 2023
• Online Publication Date: Dec 3, 2023
• Publication Date: Dec 3, 2023
• Deposit Date: Oct 25, 2023
• Publicly Available Date: Dec 4, 2024
• Print ISSN: 0302-9743
• Publisher: Springer
• Volume: 14061
• Pages: 101-116
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Edition: 1
• Book Title: Algorithmics of Wireless Networks: 19th International Symposium, ALGOWIN 2023, Amsterdam, The Netherlands, September 7–8, 2023, Revised Selected Papers
• ISBN: 9783031488818
• DOI: https://doi.org/10.1007/978-3-031-48882-5_8
• Public URL: https://durham-repository.worktribe.com/output/1816807
• Related Public URLs: https://arxiv.org/abs/2306.06999