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.SAND.2022.22
URN: urn:nbn:de:0030-drops-159644
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15964/
Go to the corresponding LIPIcs Volume Portal

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

Brief Announcement: The Temporal Firefighter Problem

pdf-format:
LIPIcs-SAND-2022-22.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{hand_et_al:LIPIcs.SAND.2022.22,
  author =	{Hand, Samuel D. and Enright, Jessica and Meeks, Kitty},
  title =	{{Brief Announcement: The Temporal Firefighter Problem}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{22:1--22:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15964},
  URN =		{urn:nbn:de:0030-drops-159644},
  doi =		{10.4230/LIPIcs.SAND.2022.22},
  annote =	{Keywords: Temporal graphs, Spreading processes, Parameterised complexity}
}

Keywords: Temporal graphs, Spreading processes, Parameterised complexity
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

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