LIPIcs.FUN.2022.15.pdf
- Filesize: 0.71 MB
- 15 pages
Document
Making Life More Confusing for Firefighters
Authors
Samuel D. Hand 
,
Jessica Enright ,
Kitty Meeks
-
Part of:
Volume:
11th International Conference on Fun with Algorithms (FUN 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-05-23
File
Document Identifiers
Author Details
Cite AsGet BibTex
Samuel D. Hand, Jessica Enright, and Kitty Meeks. Making Life More Confusing for Firefighters. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.15
https://doi.org/10.4230/LIPIcs.FUN.2022.15
Abstract
It is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem is NP-Complete on all but a few classes of graphs. Thankfully, firefighters do not have to work alone, and are often aided by the efforts of good natured civillians who slow the spread of a fire by maintaining firebreaks when they are able. We will show that this help, although well-intentioned, unfortunately makes the optimal deployment of firefighters an even harder problem. To model this scenario we introduce the Temporal Firefighter problem, 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 polynomial time solutions. This motivates us to explore making use of the temporal structure of the graph in our search for tractability, and we conclude by presenting an FPT algorithm for Temporal Firefighter 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
- Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximability of the firefighter problem - computing cuts over time. Algorithmica, 62(1-2):520-536, 2012. URL: https://doi.org/10.1007/s00453-010-9469-y.
- Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. CoRR, abs/1602.06411, 2016. URL: http://arxiv.org/abs/1602.06411.
- Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, and Erik Jan van Leeuwen. Parameterized complexity of firefighting. J. Comput. Syst. Sci., 80(7):1285-1297, 2014. URL: https://doi.org/10.1016/j.jcss.2014.03.001.
- Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Samuel Pierre, Michel Barbeau, and Evangelos Kranakis, editors, Ad-Hoc, Mobile, and Wireless Networks, Second International Conference, ADHOC-NOW 2003 Montreal, Canada, October 8-10, 2003, Proceedings, volume 2865 of Lecture Notes in Computer Science, pages 259-270. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-39611-6_23.
- Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci., 14(2):267-285, 2003. URL: https://doi.org/10.1142/S0129054103001728.
- Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. CoRR, abs/2103.05387, 2021. URL: http://arxiv.org/abs/2103.05387.
- Leizhen Cai, Elad Verbin, and Lin Yang. Firefighting on trees: (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings, volume 5369 of Lecture Notes in Computer Science, pages 258-269. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-92182-0_25.
- Janka Chlebíková and Morgan Chopin. The firefighter problem: Further steps in understanding its complexity. Theor. Comput. Sci., 676:42-51, 2017. URL: https://doi.org/10.1016/j.tcs.2017.03.004.
- 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.
- Stephen Finbow and Gary MacGillivray. The firefighter problem: a survey of results, directions and questions. Australas. J Comb., 43:57-78, 2009. URL: http://ajc.maths.uq.edu.au/pdf/43/ajc_v43_p057.pdf.
- Fedor V. Fomin, Pinar Heggernes, and Erik Jan van Leeuwen. Making life easier for firefighters. In Evangelos Kranakis, Danny Krizanc, and Flaminia L. Luccio, editors, Fun with Algorithms - 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings, volume 7288 of Lecture Notes in Computer Science, pages 177-188. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-30347-0_19.
- 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.
- Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. Adapting the bron-kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min., 7(1):35:1-35:16, 2017. URL: https://doi.org/10.1007/s13278-017-0455-0.
- Petter Holme and Jari Saramäki. Temporal networks. CoRR, abs/1108.1780, 2011. URL: http://arxiv.org/abs/1108.1780.
- 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.
- Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math., 12(4):239-280, 2016. URL: https://doi.org/10.1080/15427951.2016.1177801.
- Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data Eng., 28(11):2927-2942, 2016. URL: https://doi.org/10.1109/TKDE.2016.2594065.