LIPIcs.SAND.2022.22.pdf
- Filesize: 0.57 MB
- 3 pages
Document
Brief Announcement: The Temporal Firefighter Problem
Authors
Samuel D. Hand 
,
Jessica Enright ,
Kitty Meeks
-
Part of:
Volume:
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-04-29
File
Document Identifiers
Author Details
Cite As Get BibTex
Samuel D. Hand, Jessica Enright, and Kitty Meeks. Brief Announcement: The Temporal Firefighter Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 22:1-22:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.22
Abstract
The Firefighter problem asks how many vertices can be saved from a fire spreading over the vertices of a graph. At timestep 0 a vertex begins burning, then on each subsequent timestep a non-burning vertex is chosen to be defended, and the fire then spreads to all undefended vertices that it neighbours. The problem is NP-Complete on arbitrary graphs, however existing work has found several graph classes for which there are polynomial time solutions. We introduce Temporal Firefighter, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have a polynomial-time solution. This motivates us to explore restrictions on the temporal structure of the graph, and we find that Temporal Firefighter is fixed parameter tractable with respect to the temporal graph parameter vertex-interval-membership-width.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- Temporal graphs
- Spreading processes
- Parameterised complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. CoRR, abs/2103.05387, 2021. URL: http://arxiv.org/abs/2103.05387.
- Stephen Finbow, Andrew D. King, Gary MacGillivray, and Romeo Rizzi. The firefighter problem for graphs of maximum degree three. Discret. Math., 307(16):2094-2105, 2007. URL: https://doi.org/10.1016/j.disc.2005.12.053.
- Fedor V. Fomin, Pinar Heggernes, and Erik Jan van Leeuwen. The firefighter problem on graph classes. Theor. Comput. Sci., 613:38-50, 2016. URL: https://doi.org/10.1016/j.tcs.2015.11.024.
- Samuel Hand, Jessica Enright, and Kitty Meeks. Making life more confusing for firefighters, 2022. URL: http://arxiv.org/abs/2202.12599.
-
Bert Hartnell. Firefighter! an application of domination. In the 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Minitoba, Winnipeg, Cadada, 1995, 1995.
- David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64(4):820-842, 2002. URL: https://doi.org/10.1006/jcss.2002.1829.