On structural parameterizations of firefighting

• Published in: Theoretical computer science 2019-08, Vol.782, p.79-90
• Main Authors: Das, Bireswar, Enduri, Murali Krishna, Kiyomi, Masashi, Misra, Neeldhara, Otachi, Yota, Reddy, I. Vinod, Yoshimura, Shunya
• Format: Article
• Language: English
• Subjects: Firefighting; Kernelization; NP-complete; Parameterized complexity
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2019.02.032

The Firefighting problem is defined as follows. At time t=0, a fire breaks out at a vertex of a graph. At each time step t≥1, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The Firefighting problem turns out to be NP-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the Firefighting problem admits a polynomial-time algorithm. To begin with, we show that the problem is W[1]-hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable (FPT) when parameterized by the size of a modulator to cographs, threshold graphs and disjoint unions of stars. We further investigate the kernelization complexity of the problem and show that it does not admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions.