License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.135
URN: urn:nbn:de:0030-drops-74968
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7496/
Go to the corresponding LIPIcs Volume Portal

Choudhari, Jayesh ; Dasgupta, Anirban ; Misra, Neeldhara ; Ramanujan, M. S.

Saving Critical Nodes with Firefighters is FPT

pdf-format:
LIPIcs-ICALP-2017-135.pdf (0.5 MB)

Abstract

We consider the problem of firefighting to save a critical subset of nodes. The firefighting game is a turn-based game played on a graph, where the fire spreads to vertices in a breadth-first manner from a source, and firefighters can be placed on yet unburnt vertices on alternate rounds to block the fire. In this work, we consider the problem of saving a critical subset of nodes from catching fire, given a total budget on the number of firefighters.

We show that the problem is para-NP-hard when parameterized by the size of the critical set. We also show that it is fixed-parameter tractable on general graphs when parameterized by the number of firefighters.
We also demonstrate improved running times on trees and establish that the problem is unlikely to admit a polynomial kernelization (even when restricted to trees). Our work is the first to exploit the connection between
the firefighting problem and the notions of important separators and tight separator sequences.

Finally, we consider the spreading model of the firefighting game, a closely related problem, and show that the problem of saving a critical set parameterized by the number of firefighters is W[2]-hard, which contrasts our FPT result for the non-spreading model.

BibTeX - Entry

@InProceedings{choudhari_et_al:LIPIcs:2017:7496,
  author =	{Jayesh Choudhari and Anirban Dasgupta and Neeldhara Misra and M. S. Ramanujan},
  title =	{{Saving Critical Nodes with Firefighters is FPT}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{135:1--135:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7496},
  URN =		{urn:nbn:de:0030-drops-74968},
  doi =		{10.4230/LIPIcs.ICALP.2017.135},
  annote =	{Keywords: firefighting, cuts, FPT, kernelization}
}

Keywords: firefighting, cuts, FPT, kernelization
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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