On structural parameterizations of firefighting

Show simple item record

dc.contributor.author Das, Bireswar
dc.contributor.author Enduri, Murali Krishna
dc.contributor.author Kiyomi, Masashi
dc.contributor.author Misra, Neeldhara
dc.contributor.author Otachi, Yota
dc.contributor.author Reddy, I. Vinod
dc.contributor.author Yoshimura, Shunya
dc.date.accessioned 2019-03-27T06:42:07Z
dc.date.available 2019-03-27T06:42:07Z
dc.date.issued 2019-03
dc.identifier.citation Das, Bireswar; Enduri, Murali Krishna; Kiyomi, Masashi; Misra, Neeldhara; Otachi, Yota; Reddy, I. Vinod and Yoshimura, Shunya,"On structural parameterizations of firefighting", Theoretical Computer Science, DOI: 10.1016/j.tcs.2019.02.032, Mar. 2019. en_US
dc.identifier.issn 0304-3975
dc.identifier.uri https://doi.org/10.1016/j.tcs.2019.02.032
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/4289
dc.description.abstract he Firefighting problem is defined as follows. At time , a fire breaks out at a vertex of a graph. At each time step, 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-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 -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 () when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions.
dc.description.statementofresponsibility by Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi,Neeldhara Misra, Yota Otachi, I. Vinod Reddy, and Shunya Yoshimura
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.subject Firefighting en_US
dc.subject Parameterized complexity en_US
dc.subject NP-complete en_US
dc.subject Kernelization en_US
dc.title On structural parameterizations of firefighting en_US
dc.type Article en_US
dc.relation.journal Theoretical Computer Science

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account