Document Open Access Logo

Saving Critical Nodes with Firefighters is FPT

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.135.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Jayesh Choudhari
Anirban Dasgupta
Neeldhara Misra
M. S. Ramanujan

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ICALP.2017.135

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.
Keywords
  • firefighting
  • cuts
  • FPT
  • kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximation algorithms for the firefighter problem: Cuts over time and submodularity. In International Symposium on Algorithms and Computation, pages 974-983. Springer, 2009. Google Scholar
  2. Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R Fellows, Fedor V Fomin, and Erik Jan van Leeuwen. Parameterized complexity of firefighting. Journal of Computer and System Sciences, 80(7):1285-1297, 2014. Google Scholar
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  4. Leizhen Cai, Elad Verbin, and Lin Yang. Firefighting on trees:(1- 1/e)-approximation, fixed parameter tractability and a subexponential algorithm. In International Symposium on Algorithms and Computation, pages 258-269. Springer, 2008. Google Scholar
  5. Center for Disease Control. People at High Risk of Developing Flu-Related Complications. https://www.cdc.gov/flu/about/disease/high_risk.htm, 2016.
  6. Parinya Chalermsook and Julia Chuzhoy. Resource minimization for fire containment. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1334-1349. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  7. Morgan Chopin. Optimization problems with propagation in graphs: Parameterized complexity and approximation. PhD thesis, Université Paris Dauphine-Paris IX, 2013. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D 'aniel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, Cham, Cham, 2015. Google Scholar
  10. Marek Cygan, Fedor V Fomin, and Erik Jan van Leeuwen. Parameterized Complexity of Firefighting Revisited. In Parameterized and exact computation, pages 13-26. Springer, Heidelberg, Berlin, Heidelberg, 2012. Google Scholar
  11. Reinhard Diestel. Graph Theory. Springer Graduate Text GTM 173. Reinhard Diestel, July 2012. Google Scholar
  12. Robert J Ellison, David A Fisher, Richard C Linger, Howard F Lipson, and Thomas Longstaff. Survivable network systems: An emerging discipline. Technical report, DTIC Document, 1997. Google Scholar
  13. S Finbow, B Hartnell, Q Li, and K Schmeisser. On minimizing the effects of fire or a virus on a network. Journal of Combinatorial Mathematics and Combinatorial Computing, 33:311-322, 2000. Google Scholar
  14. Stephen Finbow and Gary MacGillivray. The firefighter problem: a survey of results, directions and questions. The Australasian Journal of Combinatorics, 43:57-77, 2009. Google Scholar
  15. Howard Frank and I Frisch. Analysis and design of survivable networks. IEEE Transactions on Communication Technology, 18(5):501-519, 1970. Google Scholar
  16. Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Discovering archipelagos of tractability for constraint satisfaction and counting. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670-1681, 2016. Google Scholar
  17. Bert Hartnell. Firefighter! an application of domination. In 25th Manitoba Conference on Combinatorial Mathematics and Computing, 1995. Google Scholar
  18. Andrew King and Gary MacGillivray. The firefighter problem for cubic graphs. Discrete Mathematics, 310(3):614-621, 2010. Google Scholar
  19. Daniel Lokshtanov and M. S. Ramanujan. Parameterized tractability of multiway cut with parity constraints. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 750-761, 2012. Google Scholar
  20. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for directed feedback vertex set. CoRR, abs/1609.04347, 2016. Google Scholar
  21. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for node unique label cover. CoRR, abs/1604.08764, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact