2026-08-16T22:30:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7496 2024-03-06T10:40:34Z ddc:004 open_access

Saving Critical Nodes with Firefighters is FPT Choudhari, Jayesh Dasgupta, Anirban Misra, Neeldhara Ramanujan, M. S. firefighting cuts FPT kernelization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jayesh Choudhari and Anirban Dasgupta and Neeldhara Misra and M. S. Ramanujan 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.135 urn:nbn:de:0030-drops-74968 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.135 eng https://creativecommons.org/licenses/by/3.0/legalcode