Parameterized Complexity of Firefighting Revisited

DOI10.1007/978-3-642-28050-4_2MaRDI QIDQ2891334zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen

Publication date 15 June 2012

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be permanently placed on an unburned vertex and the fire spreads to its neighborhood in the graph in so far no firefighters are protecting those vertices. The goal is to let as few vertices burn as possible. This problem is known to be NP-complete, even when restricted to bipartite graphs or to trees of maximum degree three. Initial study showed the Firefighter problem to be fixed-parameter tractable on trees in various parameterizations. We complete these results by showing that the problem is in FPT on general graphs when parameterized by the number of burned vertices, but has no polynomial kernel on trees, resolving an open problem. Conversely, we show that the problem is W[1]-hard when parameterized by the number of unburned vertices, even on bipartite graphs. For both parameterizations, we additionally give refined algorithms on trees, improving on the running times of the known algorithms.

Recommendations

• Parameterized complexity of firefighting
• Parameterized complexity of the firefighter problem
• The firefighter problem: further steps in understanding its complexity
• Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment
• Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment
• Approximability of the firefighter problem. Computing cuts over time
• The Firefighter problem: a survey of results, directions and questions
• A new model and algorithms in firefighting theory

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Cross-composition: a new technique for kernelization lower bounds
• Diameter and treewidth in minor-closed graph families
• Easy problems for tree-decomposable graphs
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• scientific article; zbMATH DE number 1506515 (Why is no real title available?)
• On problems without polynomial kernels
• Parameterized complexity of the firefighter problem
• The firefighter problem for graphs of maximum degree three
• The Firefighter problem: a survey of results, directions and questions
• Towards more efficient infection and fire fighting

Cited in

(11)

• Parameterized complexity of graph burning
• Parameterized complexity of firefighting
• Parameterized complexity of the firefighter problem
• The firefighter problem: empirical results on random graphs
• Saving critical nodes with firefighters is FPT
• The firefighter problem: further steps in understanding its complexity
• Politician’s Firefighting
• Firefighting as a strategic game
• A matheuristic for the firefighter problem on graphs
• Parameterized Complexity of Graph Burning
• The firefighter problem on graph classes

This page was built for publication: Parameterized Complexity of Firefighting Revisited

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