Parameterized complexity of the firefighter problem

Cristina Bazgan, Morgan Chopin, Michael Fellows

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    Abstract

    In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k -Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k-Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k-Vertices.
    Original languageEnglish
    Title of host publicationProceedings of the 22nd International Symposium on Algorithms and Computation
    EditorsTakao Asano, Shin-ichi Nakano, Yoshio Okamoto, Osamu Watanabe
    Place of PublicationGermany
    PublisherSpringer
    Pages643-652
    Number of pages10
    DOIs
    Publication statusPublished - 2011
    EventInternational Symposium on Algorithms and Computation (ISAAC 2011 22nd) - Japan, Japan
    Duration: 5 Dec 20118 Dec 2011
    Conference number: 2011 (22nd)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume7074
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Symposium on Algorithms and Computation (ISAAC 2011 22nd)
    Abbreviated titleISAAC
    CountryJapan
    Period5/12/118/12/11

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

    Cite this