DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2017.135

Saving Critical Nodes with Firefighters is FPT

Authors: Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, and M. S. Ramanujan

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.

Cite as

Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, and M. S. Ramanujan. Saving Critical Nodes with Firefighters is FPT. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 135:1-135:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{choudhari_et_al:LIPIcs.ICALP.2017.135,
  author =	{Choudhari, Jayesh and Dasgupta, Anirban and Misra, Neeldhara and Ramanujan, M. S.},
  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 =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.135},
  URN =		{urn:nbn:de:0030-drops-74968},
  doi =		{10.4230/LIPIcs.ICALP.2017.135},
  annote =	{Keywords: firefighting, cuts, FPT, kernelization}
}

Search Results

Documents authored by Choudhari, Jayesh

Saving Critical Nodes with Firefighters is FPT

Abstract

Cite as

Thanks for your feedback!

Could not send message