Saving critical nodes with firefighters is FPT

DOI10.4230/LIPICS.ICALP.2017.135zbMATH Open1442.68165arXiv1705.10923OpenAlexW2963193271MaRDI QIDQ5111467FDOQ5111467

Author name not available (Why is that?)

Publication date: 27 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1705.10923

Recommendations

• Parameterized Complexity of Firefighting Revisited
• Parameterized complexity of firefighting
• On structural parameterizations of firefighting
• The firefighter problem on graph classes
• On structural parameterizations of firefighting

zbMATH Keywords

kernelizationFPTcutsfirefighting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (2)

• Title not available (Why is that?)
• Deletion to scattered graph classes. I: Case of finite number of graph classes

This page was built for publication: Saving critical nodes with firefighters is FPT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111467)