License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.15
URN: urn:nbn:de:0030-drops-159851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15985/
Go to the corresponding LIPIcs Volume Portal

Hand, Samuel D. ; Enright, Jessica ; Meeks, Kitty

Making Life More Confusing for Firefighters

pdf-format:
LIPIcs-FUN-2022-15.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{hand_et_al:LIPIcs.FUN.2022.15,
  author =	{Hand, Samuel D. and Enright, Jessica and Meeks, Kitty},
  title =	{{Making Life More Confusing for Firefighters}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15985},
  URN =		{urn:nbn:de:0030-drops-159851},
  doi =		{10.4230/LIPIcs.FUN.2022.15},
  annote =	{Keywords: Temporal graphs, Spreading processes, Parameterised complexity}
}

Keywords: Temporal graphs, Spreading processes, Parameterised complexity
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI