Temporal Reachability Dominating Sets: contagion in temporal graphs
| Title: | Temporal Reachability Dominating Sets: contagion in temporal graphs |
|---|---|
| Authors: | Kutner, David C., Larios-Jones, Laura |
| Publication Year: | 2023 |
| Collection: | Computer Science Mathematics |
| Subject Terms: | Computer Science - Discrete Mathematics, Computer Science - Computational Complexity, Mathematics - Combinatorics |
| More Details: | 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 $\tau$ of the graph, the number of locally earliest edges in the graph, and the treewidth of the footprint graph $\mathcal{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 $\Sigma_2^P$-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. Comment: 38 pages, 17 figures |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2306.06999 |
| Accession Number: | edsarx.2306.06999 |
| Database: | arXiv |
| Description not available. |