Parameterized complexity of firefighting

Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael Fellows, Fedor Fomin, Erik van Leeuwen

    Research output: Contribution to journalArticle

    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 placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b?1 firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.
    Original languageEnglish
    Pages (from-to)1285-1297
    Number of pages13
    JournalJournal of Computer and System Sciences
    Volume80
    Issue number7
    DOIs
    Publication statusPublished - Nov 2014

    Fingerprint Dive into the research topics of 'Parameterized complexity of firefighting'. Together they form a unique fingerprint.

    Cite this