On Structural Parameterizations of Firefighting
Bireswar Das, Murali Krishna Enduri? , Neeldhara Misra?? and I. Vinod Reddy

arXiv:1711.10227v1 [cs.DS] 28 Nov 2017

IIT Gandhinagar, India
{bireswar,endurimuralikrishna,neeldhara.m,reddy vinod}@iitgn.ac.in

Abstract. 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 > 0, a

firefighter permanently defends (protects) an unburned vertex, and the
fire then spread 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. Specifically, for a graph
class F and a graph G, a vertex subset S is called a modulator to F if
G \ S belongs to F. The parameters we consider are the sizes of modulators to graph classes such as threshold graphs, bounded diameter graphs,
disjoint unions of stars, and split graphs.
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 threshold graphs and disjoint unions of
stars, which are subclasses of diameter at most two graphs. We further
investigate the kernelization complexity of these problems to find that
Firefighting admits a polynomial kernel when parameterized by the
size of a modulator to a clique, while it is unlikely to admit a polynomial
kernel when parameterized by the size of a modulator to a disjoint union
of stars.

1

Introduction

The Firefighting problem was introduced by Hartnell [16] to model the spread
of diseases and computer viruses. It is a turn-based game between two players
(the “fire” and the “firefighter”), which is played on a graph G as follows. Initially,
at time t=0, a fire starts at a vertex s, at each following time step the following
happens. A firefighter defends one vertex which is not on fire, and the fire then
?
??

Supported by Tata Consultancy Services (TCS) research fellowship.
Supported by a DST-INSPIRE Fellowship.

spreads from each burning vertex to all its undefended neighbors. Once a vertex
is defended it remains so for all time intervals. The process stops when the
fire can no longer spread. The natural algorithmic question associated with this
game is to find a strategy that optimizes some desirable criteria, for instance,
maximizing the number of saved vertices [5], minimizing the number of rounds,
the number of firefighters per round [6], or the number of burned vertices [10,5],
and so on. These questions are well-studied in the literature, and while most
variants are NP-hard, approximation and parameterized algorithms have been
proposed for various scenarios. In this work, we will focus on the goal of finding a
sequence of defending vertices that maximizes the number of saved (not burned)
vertices and we refer to this as the Firefighting problem. We also use Saving
k-Vertices to refer to the decision version of this problem, where we are given
a demand k and the goal is to save at least k vertices.
We study the parameterized complexity of Firefighting with respect to
various structural parameters. In particular, our focus is on distance-to-triviality
parameterizations, wherein we identify classes of graphs on which the Firefighting problem is solvable in polynomial time, and understand the parameterized complexity of the problem parameterized by the distance of a graph to
these graph classes. In this paper, our notion of distance to a graph class in the
vertex deletion distance. More precisely, for a class F of graphs, we say that X is
an F-modulator of a graph G if there is a subset X ⊆ V(G) such that G \ X ∈ F. If
the size of a smallest modulator to F is k, we also say that the distance of G to
the class F is k. Throughout this paper, we will assume that a modulator is given
to us as a part of the input. This assumption is without loss of generality since
such modulators can be computed in FPT time. We are now ready to describe
our results.
Our Contributions. The Firefighting problem is FPT when parameterized by
the vertex cover and distance to a clique parameterizations. On the other hand,
it is para-NP-hard when parameterized by feedback vertex set, tree-width and
clique-width [11]. However, the parameter vertex cover is very restrictive and
significantly large for dense graphs. This motivates us to consider parameters
that are intermediate between vertex cover and clique-width. In this spirit, Ganian [15] studied the parameterized complexity of Firefighting problem for
parameter twin-cover which is a generalization of vertex cover and showed that
Firefighting is FPT with respect to twin-cover. Recently Chlebı́ková et al. [7]
showed that the problem is FPT parameterized by distance to cluster graphs
which is a generalization of twin-cover.
We study the parameterized complexity of the Firefighting problem with
respect to the distance from following graph classes: threshold graphs, disjoint
union of stars, disjoint union of graphs of diameter at most two, and split graphs.
Studying the parameterized complexity of Firefighting with respect to these
parameters improves the understanding of the boundary between tractable and
intractable parameterizations. For instance, the parameterization by distance to
cluster graphs (as studied by [7]) directly generalizes both vertex cover and distance to clique. Observe that cluster graphs are precisely the graphs whose con2

W[1]-hard

Para NP-hard

Distance to

Rank-width,
Clique-width

diameter ≤ 3 graphs*
Tree-width

Distance to
split graphs *

Feedback
vertex set

Distance to
diameter ≤ 2 graphs*

Distance
to cographs

Distance
to cluster

FPT

Distance
to stars*

Distance to
threshold graphs *

No Poly-kernel
Twin cover

Distance
to clique *

Vertex cover

Poly-kernel

Fig. 1 A schematic showing the parameterized complexity of Firefighting
with respect to various structural graph parameters. There is a line between two
parameters if the parameter below is larger than the parameter above. Results
shown in this paper are marked by an asterisk (*).

nected components have diameter one, and a natural generalization to consider
is the class of graphs whose connected components have diameter two. Here, we
show that there is a transition in complexity: the problem becomes W[1]-hard.
As a natural intermediate problem, we consider the subclass of graphs where
every connected component is a star. Here, using ideas similar to the ones that
lead to the FPT algorithm for the distance to cluster parameter, we obtain a FPT
algorithm. The case analysis here is more delicate because we have to distinguish
between the central vertex and the leaves.
1
On the other hand, the distance to threshold graphs parameter directly generalizes the distance to clique parameter, while the distance to stars parameter
is a generalization of vertex cover. For both of these parameters, we establish
that Firefighting is FPT. These being smaller parameters, our results improve
several known algorithms. Note that the next “natural” parameter to consider
after distance to stars hierarchy is the feedback vertex number, or the distance to
forests; however here the problem is already NP-hard on trees, leading to paraNP-hardness. Similarly, a natural next step from distance to threshold graphs is
the distance to split graphs, but here also we demonstrate W[1]-hardness. Finally,
a promising generalization from the distance to cluster graphs is the distance to
cographs, and here we leave the parameterized complexity of the problem open.
3

We also consider the kernelization complexity of the problem and make the
following advances: for the distance to clique parameterization, we demonstrate a
quadratic kernel, while for the distance to stars parameterization, we show that a
polynomial kernel is unlikely under standard complexity-theoretic assumptions.
The kernelization complexity of the problem relative to vertex cover, however,
remains an interesting open problem. We summarize our results below.
• We show that the problem is fixed parameter tractable (FPT) when param-

eterized by the size of a modulator to threshold graphs, cluster graphs and
disjoint unions of stars.
• We further investigate the kernelization complexity of these problems to find
that Firefighting admits a polynomial kernel when parameterized by the size
of a modulator to a clique, while it is unlikely to admit a polynomial kernel
when parameterized by the size of a modulator to a disjoint union of stars.
• Finally, in contrast to the tractability results, we show that Firefighting
is W[1]-hard when parameterized by the distance to split graphs. In fact,
the problem remains W[1]-hard with respect to the combined parameter
involving the size of the modulator and the number of vertices to be saved.
Methodology. By and large, we use a standard approach for the FPT algorithms:
we guess the behavior of the solution on the modulator and attempt to find a
solution consistent with the guessed behavior. The second part relies on exploiting the structural properties of G \ X, which is the part of the graph outside
the modulator. Usually one is able to group the vertices of G \ X based on the
structure of their neighborhoods in the modulator, and argue that all vertices
of the same “type” have a similar behavior, which leads to a controlled search
space. In the case of threshold graphs, we are able to prove that simple greedy
techniques work within a particular type. On the other hand, for disjoint unions
of stars, we have to account for several scenarios, and the classification of G \ X
is more intricate, and accordingly, we have to account for more cases in the
analysis. The hardness results follow from reductions using standard techniques,
while the kernelization algorithm uses the fact that when G \ X is a large clique,
several vertices behave in a similar fashion, and this observation allows us to
replace the large clique with a much smaller one — a careful argument is required, however, to demonstrate that the instance we constructed in this fashion
is indeed equivalent to the original.
Related Work. The Firefighting problem is known to be NP-hard even for
special classes of graphs, including bipartite graphs [19], trees of maximum degree three [11] and cubic graphs [17]. The firefighter problem can be solved in
linear time on split graphs and co-graphs [14]. From the parameterized complexity point of view, the firefighting problem is W[1]-hard when parameterized
by the number of saved vertices for bipartite graphs [1]. Cai et al. [5] propose
several FPT algorithms and polynomial kernels, and they consider the following
parameters: the number of saved vertices, the number of saved leaves, and the
number of protected vertices. Leung [18] use the random separation method to
4

give FPT algorithms on general graphs parameterized by the number of burnt
vertices and on degree bounded graphs and unicyclic graphs parameterized by
the number of protected vertices. We refer the reader to the survey [12], as well
as the references within, for more details.

2

Preliminaries

In this section, we introduce the notation and the terminology that we will need
to describe our algorithms. Most of our notation is standard. We use [k] to
denote the set {1, 2, . . . , k}. All graphs we consider in this paper are undirected,
connected, finite and simple. For a graph G = (V, E), let V(G) and E(G) denote
the vertex set and edge set of G respectively. An edge in E between vertices x
and y is denoted as xy for simplicity. For a subset X ⊆ V(G), the graph G[X]
denotes the subgraph of G induced by vertices of X. Also, we abuse notation
and use G \ X to refer to the graph obtained from G after removing the vertex
set X. For a vertex v ∈ V(G), N(v) denotes the set of vertices adjacent to v and
N[v] = N(v) ∪ {v} is the closed neighborhood of v.
Graph Classes. We now define the graph classes that we will encounter frequently.
• A graph is a split graph if its vertices can be partitioned into a clique and
an independent set. Split graphs are P5 -free [13].
• The class of P4 -free graphs are called co-graphs.
• A graph is a threshold graph if it can be constructed recursively by adding

an isolated vertex or a universal vertex.
• A cluster graph is a disjoint union of complete graphs. Cluster graphs are
also P3 -free graphs.

It is easy to see that a graph that is both split and co-graph is a threshold
graph. We denote threshold graph (or a split graph) with G = (C, I) where C
and I denote a partition of G into a clique and an independent set. For any two
vertices x, y in a threshold graph G we have either N(x) ⊆ N[y] or N(y) ⊆ N[x].
For a class of graphs F, the distance to F of a graph G is the minimum number
of vertices to be deleted from G to get a graph in F.
Parameterized Complexity. A parameterized problem is a pair Q ⊆ Σ∗ × N,
where Σ is fixed finite alphabet. For an instance (x, k) ∈ Σ∗ × N, k is called the
parameter. We say that a parameterized problem Q is fixed parameter tractable
(FPT) if there exists an algorithm and a computable function f : N → N such
that given (x, k) ∈ Σ∗ × N the algorithm correctly decides whether (x, k) ∈ Q in
f(k)|(x, k)|O(1) time. The function f is usually superpolynomial and only depends
on parameter k. The class XP contains the problems which are solvable in time
|(x, k)|f(k) , the exponent of the running time depends on the parameter k. A
problem is para-NP-hard if it is NP-hard for some fixed values of the parameter.
The complexity class of parameterized intractability is called W[1] (see [9] for
5

the definition). A kernelization algorithm is a polynomial time algorithm that
takes an instance (x, k) of a parameterized problem Q as input and outputs
an equivalent instance (x 0 , k 0 ) of P such that |x 0 | 6 h(k) for some computable
function h and k 0 6 k. If h is polynomial then we say that (x 0 , k 0 ) is a polynomial
kernel. Let P and Q be two parameterized problems. A parameterized reduction
from P to Q is a mapping g : Σ∗ → Σ∗ such that (i) for all x ∈ Σ∗ we have x
is a yes instance of P ⇔ g(x) is a yes instance of Q. (ii) g can be computed in
f(k)|x|O(1) time, where f is computable function and k is the parameter of x. (iii)
k 0 6 h(k) for some computable function h, where k and k 0 are parameters of x
and g(x) respectively. For more details on parameterized complexity the reader
is referred to [9,8].
We now briefly justify our assumption about the modulators being given as
a part of the input to our problems. Consider the following result.
Lemma 1. [4] Let F be a graph class characterized by the finite forbidden induced subgraphs H1 , · · · , Hl . Given a graph G and integer k, there is an FPT
algorithm that finds a subset X ⊆ V(G) of size at most k such that G \ X ∈ F in
O(dk nd ), where d is the size of largest forbidden subgraph.
The class of cluster graphs, threshold graphs and split graphs are P3 , P4 are
P5 free respectively. By using above lemma, Given a graph G and integer k, the
problem of deciding whether there exists a set X of vertices of size at most k
whose deletion results in a cluster graph, threshold graph and split graph is fixed
parameter tractable.
The Firefighting Problem. Finally, we formally define the problems that we consider in this paper, where F is a class of graphs or a graph property.
Firefighting[F]
Input: A graph G, a vertex s, a modulator X ⊆ V(G) such
that G \ X ∈ F.
Parameter: The size k := |X| of the modulator to F.
Question: Find a strategy that maximizes the number of saved
vertices when a fire starts at s?

Saving k-Vertices[F]
Input: A graph G, a vertex s, a modulator X ⊆ V(G) such
that G \ X ∈ F, and an integer k.
Parameter: The size ` := |X| of the modulator to F.
Question: Does there exists a strategy that saves at least k vertices when a fire starts at s?
Whenever F is clear from the context, we drop the explicit mention of it in
the name of the problem. We also abuse notation and use k differently in the
6

two definitions, to retain consistency with standard notation when we present
reductions in the context of Saving k-Vertices.

3

The Parameterized Complexity of Firefighting

Let (G, s) be an instance of Firefighting problem. The vertices that have
not been burned by the fire at the end of the process are called saved (including
defended vertices). A vertex is burned if it is on fire. A strategy for Firefighting
instance (G, s) is a sequence S of vertices {v1 , · · · , vl } where vi represents the
position of the firefighter at time step i. We say that sequence S is a valid
strategy for (G, s) if vertex vi is not burning at the start of time step i and the
process stops at time step l. A strategy S is called minimal if no subset of S
yields a strategy that saves same number of vertices as S. A strategy is optimal
if it is minimal and saves maximum number of vertices.
The following results from the literature will be useful for our algorithms.
Lemma 2. [14] Let G be a graph and s be a vertex of G. Given an ordered set S
of vertices of G, we can verify whether S is a valid strategy for the Firefighting
problem on (G, s) and count the number of vertices saved by S in O(n + m) time,
where n and m denote the number of vertices and edges in G respectively.
Proof. Let S = {v1 , · · · , vk } is strategy in this order. To verify whether the sequence S is a valid strategy, we do BFS on the graph G starting from s. Find the
distance d(s, v) from the source s to each vertex v of S on graph G[(V(G) \ S)∪ {v}].
For i = 1 to k, If S is a valid strategy then distance from source s to the vertex
vi , d(s, vi ) > i, otherwise vertex vi will be burned before time step i. Observe
that the number of vertices burned by S in G equal to the number of vertices
reachable from s in G \ S, which can be found by applying BFS on the graph
G \ S starting from s.
t
u
Corollary 1. Let S be an optimal strategy for the Firefighting problem on
(G, s) then the number of vertices burned by S in G is equal to the number of
vertices reachable from s in G \ S.
Lemma 3. [14] Let (G, s) be an instance of the Firefighting problem, and let
l be the length of a longest induced path in G starting from s. Then any optimal
strategy can defend at most l vertices.
Proof. Let S = {v1 , · · · , vt } be an optimal strategy defended in this order. Since
S is a valid strategy there is an induced path P from s to vt such that all the
vertices on P are burned except vt . Let P be a shortest such path, then P contains
at least t + 1 vertices: otherwise vt will be burned before time t. Since the length
of longest induced path in G starting from s is l, we have t + 1 6 l + 1 which
implies t 6 l.
t
u
Lemma 4. [14] The Firefighting problem can be solved in O(nl ) time on
graphs with length of longest induced path is at most l − 1.
7

Proof. Let (G, s) be an instance of firefighting problem. Since the length of the
longest induced path in G is at most l. From Lemma 3 any optimal strategy can
defend at most l vertices in G. We list out all possible subsets S of V(G) of size
at most l in O(nl ) time. For each such subset S using Lemma 2 test whether
S is valid strategy and count the number of vertices saved by S. The optimal
strategy is the one which saves maximum number of vertices.
t
u
3.1

Parameterization by Distance to Threshold Graphs

In this section we give an FPT algorithm for the Firefighting problem parameterized by the distance to threshold graphs. Without loss of generality, we assume
that threshold graph is connected, otherwise all the connected components that
do not contain the source vertex are trivially saved.
Corollary 2. Let (G, s) be an instance of Firefighting problem. Then any
optimal strategy can defend at most 2k + 2 vertices, where k is the distance to
threshold graphs.
Proof. We know that fire always spreads along an induced path in G. As the
length of the longest induced path in G is at most 2k + 2, from Lemma 3 any
optimal strategy can defend at most 2k + 2 vertices in G.
t
u
Let G be a graph and X ⊆ V(G) of size k such that G \ X = (C, I) is a threshold
graph. We partition the vertices of clique C and independent set I in G \ X
based on their neighborhoods in X. In particular, for every subset Y ⊆ X, let:
TYC := {x ∈ C | N(x) ∩ X = Y } and TYI := {x ∈ I | N(x) ∩ X = Y }.
Notice that in this way we can partition vertices of G \ X into at most 2k+1
subsets (called types), two for each Y ⊆ X. Observe that all vertices in a type
have same neighbors in X, where as they may have different neighbors inside
the threshold graph. The following result shows that when we need to choose
a defending vertex from a type the best strategy is to defend a highest degree
vertex in that type. For a strategy S, let sav(S) denote the number of vertices
saved by the strategy S.
Lemma 5. Let v1 , v2 be two vertices in a type T such that N(v2 ) ⊆ N[v1 ]. Let S
be a strategy containing v2 , which is defended at time step i. If v1 ∈
/ S and not
burning at the start of time step i then sav(S) 6 sav(S 0 ) where S 0 is obtained
from S by replacing v2 with v1 at time step i.
Proof. Using Corollary 1, the vertices burned by S in G are the vertices which
are reachable from s in G \ S. We show that every vertex u which is reachable
from s in G \ S 0 is also reachable from s in G \ S. Let P be a path between s
and u in G \ S 0 . If v2 ∈
/ P then P is a path in G \ S. If v2 ∈ P, then using the
facts that v1 is a burned vertex in strategy S and N(v2 ) ⊆ N[v1 ], we can see that
P 0 = P \ {v2 } ∪ {v1 } is a path between s and u in G \ S. Therefore the number
of vertices burned by S is at least the number of vertices burned by S 0 , which
implies sav(S) 6 sav(S 0 ).
8

Our FPT algorithm now follows by guessing, for each step in the defending
sequence, if the vertex is from the modulator or the type of the vertex from
G \ X. Then it simulates the sequence (by substituting for each guess of a type,
a greedily chosen vertex from that type) to check if it is a valid solution.
Theorem 1. The Firefighting problem can be solved in O((2k+1 +k)2k+2 (n+
m)) time when parameterized by size of modulator to threshold graphs.
Proof. Partition the vertices of G \ X into at most 2k+1 sets. Each time when we
want to defend a vertex we only choose from 2k+1 (types) +k (size of X). From
Lemma 5 we know which vertex has to be defended in a given type.
From Corollary 2 it is clear that we only need to defend at most 2k + 2 times,
therefore there are at most (2k+1 + k)2k+2 possible firefighting strategies. For
each such strategy S, using Lemma 2, test whether S is valid strategy and count
the number of vertices saved by S. The strategy which saves maximum number
of vertices is the optimal strategy. Therefore this procedure takes O((2k+1 +
k)2k+2 (n + m)) time.
t
u
3.2

Parameterization by Distance to Stars

In this section we design an FPT algorithm for the Firefighting problem parameterized by the distance to stars. Recall that this is the minimum number of
vertices to be deleted from G to get a disjoint union of stars. Let X be a k-sized
modulator to disjoint union of stars. Our first observation follows easily from
the bound on the length of the longest induced path.
Corollary 3. Let (G, s) be an instance of Firefighting problem. Any optimal
strategy can defend at most 4k + 2 vertices, where k is distance to disjoint union
of stars.
Proof. We know that fire always spreads along an induced path in G. As the
length of maximum induced path in G is at most 4k + 2, from Lemma 3 any
optimal strategy can defend at most 4k + 2 vertices in G.
t
u
We now define a notion of equivalent stars, which will lead us to partitioning of
the stars in G \ X into types as before. For a star S with center c in G \ X, we
use B(S) to denote the set of vertices in S that have a neighbor in X, and call
these the border vertices. Further, for a nonempty subset Y ⊆ X, we use BY (S) to
denote the set of vertices in S whose neighborhood in X is exactly Y .
Definition 1. Let X ⊆ V(G) such that G \ X is a disjoint union of stars. We
call two stars Si and Sj are equivalent if, (a) N(ci ) = N(cj ), where ci and cj are
the centers of stars Si and Sj respectively. (b) N(Si ) = N(Sj ), (c) |B(Si )| = |B(Sj )|
and (d) For every non-empty subset Y ⊆ X, we have that |BY (Si )| = |BY (Sj )|.
For an equivalence class T , we use bT to denote the size of the border for any
star in T . Our next result bounds the number of equivalence classes. The bound
9

follows roughly from the fact that one can associate a signature with an equivalence class based on condition (c) in Definition 1, which, in turn, can be put
in one-one correspondence with strings of length 2k over an alphabet of size `,
where ` is the maximum possible value of |B(S)| in G \ X.
Lemma 6. Let ` be defined as above and let X ⊆ V(G) be a modulator to disjoint
union of stars of size k. Then, the stars of G \ X can be partitioned into at
k
most O(22k `2 ) equivalence classes.
Proof. First, partition the stars in G \ X into at most 22k sets such that all stars
in each set satisfies conditions (a) and (b) of Definition 1. Now each set of the
partition can be further divided based on the value of |B(Si )| for each star Si
in that set. As 1 6 |B(Si )| 6 ` for all Si ∈ G \ X, each set can be partitioned
into at most ` sets. In order to satisfy condition (d) in Definition 1 each set
k
k
further partitioned into `2 −1 sets. Combining all, there are at most O(22k `2 )
equivalent star partitions of stars in G \ X.
t
u
Our FPT algorithm begins by guessing the behavior of the solution on the
modulator, and builds on the fact that there are a bounded number of equivalence
classes. We defer the details of this algorithm to a full version because of space
constraints, and note that it is similar — in spirit — to the approach used for
the cluster vertex deletion parameter in [7].
Theorem 2. The Firefighting problem is FPT when parameterized by the
distance from the class of the disjoint union of stars.
Proof. Without loss of generality, assume s ∈ X: If s ∈
/ X then G \ (X ∪ {s}) is
also a disjoint union of stars. As a first step, we guess the defended (Xd ), saved
(Xs ) (which are not in Xd ) and burned (Xb ) vertices from X in O(3k ) time. Since
the length of any optimal defending sequence is at most 4k + 2, we can guess
the set of defended vertices (Xd ) from X along with their positions in an optimal
defending sequence in O(kk (4k + 2)k ) time. The rest of this proof is divided into
two cases depending on whether Xs = ∅ or Xs 6= ∅.
Case 1: Xs = ∅. Since the fire starts at s, all the vertices in V(G)\Xd which are not
reachable from s in G[V(G) \ Xd ] are saved from fire. We begin by deleting them
from G and concentrate on the connected component Cs of G \ Xd containing
the vertex s. In particular, the instance of firefighting problem that we solve
from here is (G[Cs ], s, Xb ) where Xb is the modulator to disjoint union to stars.
Also, we note at this point that if Xb = ∅, then we are done by a straightforward
case analysis on the nature of N(s) and simulating the guessed defence sequence.
Therefore, we assume that Xb 6= ∅.
Partition the stars in Cs \ Xb into equivalence classes (with respect to Xb )
using Definition 1. We divide equivalence classes of stars in Cs \ Xb into two
categories: equivalence classes with bT 6 4k + 2 as one category and remaining
as the other. We combine all equivalence classes T , with bT > 4k + 2 to into
one new equivalence class Tnew . Therefore from Lemma 6 there are at most
10

k

O(k2k (4k + 2)2 ) equivalence classes of stars in Cs \ Xb . From Corollary 3, the
length of any optimal defending sequence S is at most 4k + 2, therefore we can
defend for at most 4k + 2 time steps. Since we have already guessed defending
vertices Xd from X, the remaining defending vertices in S has to be from Cs \ Xb .
At each time step when we want to choose a defending vertex from Cs \ Xb , we
k
choose from O(k2k (4k + 2)2 ) equivalence classes. Therefore there are at most
k

O((k2k (4k + 2)2 ))

4k+2

possible firefighting defending sequences. Let S be one
such possible defending sequence, then each position of S represents either a
vertex of Xd or an equivalence class in G \ Xb .
Now we describe the procedure to select a defending vertex from an equivalence class. Let T be an equivalence class such that bT 6 4k + 2. First, count
q, the number of times T appeared in strategy S. Since T can appear at most
4k + 2 times, q 6 4k + 2. In each star, we need to defend at least one vertex so
we can defend at most 4k + 2 stars. Order the stars in T in descending order of
size |Si \ B(Si )|. We choose defending vertices from set D = ∪4k+2
i=1 (B(Si ) ∪ {ci })
(i.e, union is over first 4k + 2 stars ordered according to |Si \ B(Si )|). The size of
D is at most (4k + 2)(4k + 3).
In equivalence class Tnew , we only need to defend center of stars in Tnew . First
count q number of times Tnew is appeared in sequence S, we can only defend
centers of q different stars. Since each star center is at different distance from
source s, so we can not greedily defend center of a star for which |Si \ B(Si )| is
maximum. The defending vertex set D is defined as follows. For each i ∈ [4k + 2],
find top i stars according to size of |Si \ B(Si )| whose center is at a distance i
from source s. Add the centers of these stars to set D. It is easy to see that
|D| 6 (4k + 2)2 .
Case 2: Xs 6= ∅. Let Xs1 , Xs2 , · · · , Xsm 0 and Xb1 , Xb2 , · · · , Xbm 00 be the connected components of G[Xs ] and G[Xb ] respectively. Recall that we are working in the connected component containing s in the graph G \ Xd . Let S be a star in G \ (Xb ∪Xs ).
We say that S is vulnerable if it has at least one vertex u that has a neighbor
in Xb and at least one vertex v that has a neighbor in Xs (potentially u = v).
For any vulnerable star S, note that any firefighting strategy that respects the
semantics of Xs , Xb and Xd must defend at least one vertex in S. Indeed, suppose
not, and let S be a firefighting strategy that violates this criteria. Then after S
is executed, S has at least one undefended vertex (say p) that is a neighbor of
some vertex in Xb (say x) and one undefended vertex (say q) that is a neighbor
of some vertex in Xd (say y). Then, note that the (x, p, q, y) is a path from Xb to
Xs in the graph after the S is executed, contradicting the semantics of Xs , Xb and
Xd . Observe that this argument works even if p = q. To discuss the consequence
of this observation further, we employ the following notation:
Bb (Si ) := {x ∈ Si | N(x) ∩ Xb 6= ∅} and Bs (Si ) := {x ∈ Si | N(x) ∩ Xs 6= ∅}.

Note now that since at least one vertex has to be defended from every vulnerable star, the total number of vulnerable stars ` is at most 4k + 2.
11

We place all the vulnerable stars in one equivalence class (call this T 0 ). Now
two cases remain: the first is that every border vertex of the star S has all its
neighbors in Xs or Bb (Si ) = ∅. We place all such stars also in one equivalence
class (call this T ? ). Observe that in this case, representative vertices for the
placement of firefighters may be chosen arbitrarily. This is because the entire
star is already safe with respect to any firefighting strategy that respects the
semantics of Xb , Xs and Xd . Now consider the stars that have all their neighbors
in Xb , and note that it is not possible to save vertices in Xs by defending vertices
in such stars. Therefore, we treat such equivalence classes just as we would in
the previous case. Overall, the guess of the template sequence S happens over
the equivalence classes determined according to Definition 1 with respect to Xb
and the two special equivalence classes that we just defined, namely T ? and
T 0 . In a valid sequence, the equivalence class T 0 must appear at least ` times.
Representatives here have to be chosen from a bounded border, so a brute force
approach suffices in this situation. Representatives from T ? are chosen arbitrarily
and for all other cases they are chosen according to the description in Case 1.
To summarize, we now have a strategy for identifying a representative vertex
from each equivalence class. For each possible defending sequence S, by using
Lemma 2, we check whether it is valid and count the number of vertices of saved
by S. We output the strategy which saves the maximum number of vertices.
3.3

Parameterization by Distance to Diameter Two Graphs

In this section, we show that Saving k-Vertices is W[1]-hard when parameterized by k and distance to diameter two graphs by giving a reduction from the
k-clique problem. The reduction is similar, in spirit, to the one used in [1].
Theorem 3. Saving k-Vertices is W[1]-hard parameterized by (k + l), where
l is the distance from the class of graphs with diameter two.
Proof. Let (G, k) be a instance of k-clique problem. We construct a graph G 0
from G as follows (see Fig. 2). For each vertex v in V(G) add vertex cv in G 0 :
this set of vertices is denoted by V . For each edge (u, v) in G add a vertex iuv
in G 0 : this set of vertices is denoted by E. Add an edge from vertex iuv in E to
both vertices cu and cv in V for each (u, v) in E(G). Add a root vertex s, and
add vertices dij (set of vertices denoted by D) for 1 6 i 6 k and 1 6 j 6 k + 1.
Add edges between dij to di 0 j 0 for all i, j, j 0 and i 0 = i + 1. Connect s to d1,j for
all j and connect dk,j to each vertex in V for all j. Add a vertex z adjacent to all
vertices of V ∪ E. The vertex set of G 0 is V(G 0 ) = {s, z} ∪ D ∪ V ∪ E. It is easy
 to
see that G 0 is k(k + 1) + 1 distance to diameter two graphs. Set k 0 = k + k2 + 2
for saving vertices in G 0 .
We prove that Saving k-Vertices on (G 0 , s, k 0 ) is a yes instance if and only
if k-clique on (G, k) is a yes instance. Suppose that there is a clique K of size k in
G. Let S be a valid strategy described as follows: At each time step t = 1, · · · , k
S defends the vertices cv for all v ∈ K, at time step k + 1, S defends the vertex
z and at time step k + 2, S defends a vertex iuv , for some edge (u, v) 6∈ E(G[K]).
12

D

V

d11

d21

d31

d12

d22

d32

d13

d23

d33

E

c1
i12

3

c2

s
2

c3

i24
i34

4
c4

1

i23

5
d14

d24

i45

c5

d34
z

Fig. 2 Graph G (left) and Distance to diameter two graph G 0 (right). The vertex
z is adjacent to all vertices in V ∪ E, denoted with thick edges.



So the strategy S saves k + 1 + k2 + 1 vertices in G: k vertices in V and k2 + 1
vertices in E.
For other direction, suppose that S = {p1 , p2 , · · · , pl } is a valid strategy that
saves at least k 0 vertices in G 0 . It is easy to see that at any time step defending a
vertex dij for any i, j is not helpful, because there is at least one burning vertex
di,j 0 with same neighborhood as dij . Further defending vertices in E does not save
any vertices. Since the vertex z is universal, therefore it needs to be defended.
So the vertices in S ∩ V are responsible to save at least k2 many vertices, which
is possible only if the vertices defended in V induces k-clique in G.
t
u

We can obtain the hardness of Saving k-Vertices by a reduction from the
k-clique problem as well, in fact by making minor changes to the reduction used
to prove Theorem 3.
Corollary 4. Saving k-Vertices is W[1]-hard parameterized by (k + l), where
l is distance to split graphs.
Proof. The proof is similar to Theorem 3, except the following minor changes
in the construction of graph G 0 . Add an edge between every pair of vertices in
V and remove the universal vertex z. Add vertices dij for 1 6 i 6 k − 1 and
1 6 j 6 k. Add edges between dij to di 0 j 0 for all i, j, j 0 and i 0 = i + 1. Connects to
d1,j for all j and connect dk−1,j to each vertex in V for all j. Set k 0 = k + k2 + 1
for saving vertices in G 0 . The graph G 0 is k(k − 1) + 1 distance to a split graph.
It is easy to see that Saving k-Vertices on (G 0 , s, k 0 ) is a yes instance if and
only if k-clique on (G, k) is a yes instance.
t
u
13

4
4.1

Kernelization Complexity
Parameterization by Distance to Clique

In this section, we give a polynomial kernel for Saving k-Vertices when parameterized by distance to clique, as summarized in the following theorem.
Theorem 4. Saving k-Vertices admits a polynomial kernel of size at most
O(l2 ), where l is the distance to clique.
Let (G, s, k) be an instance of Saving k-Vertices and X ⊆ V(G) of size
l such that G \ X = C is a clique. With out loss of generality we assume that
s ∈ X, otherwise define X 0 = X ∪ {s} such that G \ X 0 is a clique with size of
modulator l + 1. Since the length of longest induced path in G is at most l + 1,
using Lemma 3 we get the following Corollary.
Corollary 5. Given an instance of Firefighting, then any optimal strategy
can defend at most l + 1 vertices, where l is size of the clique modulator X.
Let XL := {x ∈ X : |N(x) ∩ C| 6 l + 1}, XH = X \ XL . Let J := {y ∈ C | ∃x ∈
XL , y ∈ N(x)}, |J| 6 l(l + 1). Our kernelization algorithm is based on the following
observation. We show that replacing the clique G[C \ J] with another clique of
small size does not affect the solution.
Lemma 7. Let S be a valid strategy containing a vertex v ∈ C \ J, then all the
vertices of N(v) \ S are burned.
Proof. Since S is a valid strategy, there is an induced path P from s to v such
that all vertices on P are burned, except v. Let Xv := N(v) ∩ X and for every
x ∈ Xv \ S, we have |N(x) ∩ C| > l + 1: suppose there is x ∈ N(v) ∩ X such that
|N(x) ∩ C| 6 l + 1 then v ∈ J, contradiction to v ∈ C \ J.
Let u be a burned neighbor of v on P. If u ∈ C then C \ S is burned and for
every x ∈ Xv \ S, we have |N(x) ∩ C| > l + 1. From Corollary 5 we can only defend
at most l + 1 vertices, therefore all vertices of Xv \ S are burned.
If u ∈ Xv \ S then |N(u) ∩ C| > l + 1, therefore all vertices C \ S are burned.
From the first case we can see that all vertices of Xv \ S are also burned.
t
u
Reduction rules:
1. Delete vertices of C \ J from G. Add a clique K of size l + 2 and make each
vertex of K adjacent to all vertices in XH ∪ J.
2. Add another clique L of size min{l + 1, |C \ J|} and for each vertex u ∈ L, add
edges between u and J ∪ K.
Let H be the graph obtained after applying above reduction rules. It is easy
to see that X ⊆ V(H) such that H \ X is a clique. The size of the reduced instance
H is at most l2 + 4l + 3 and the reduction can be done in polynomial time.
Let C = G \ X and C 0 = H \ X. We may assume that |C \ J| > 2l + 3; otherwise,
trivially we get a kernel of size at most l2 + 4l + 3.
14

Remark 1. Let G be a graph and S be a valid strategy. If S defends a subset S1
of vertices in C \ J, then defending any subset S2 of vertices in L instead of S1 ,
with |S1 | = |S2 | is also a valid strategy S 0 for H.
Conversely let S 0 be a strategy on H. If S 0 defends a subset S1 of vertices
in K ∪ L, then defending any subset S2 of vertices in C \ J instead of S1 , with
|S1 | = |S2 | is also a valid strategy S for G.
Lemma 8. Let G and H be graphs as defined above and S, S 0 be corresponding
valid strategies as defined in the above remark. At least one vertex of C is burned
in G by strategy S iff at least one vertex of C 0 is burned in H by strategy S 0 .
Proof. Let u ∈ C 0 is burned by strategy S 0 in H. If u ∈ J, then u ∈ C will also
burned by S in G. If u ∈ K and no vertex of J burned by S 0 in H then, at least
one vertex x ∈ XH gets burned and |N(x)∩C| > l+1, therefore at least one vertex
in N(x) ∩ C gets burned by S in G.
Let u ∈ C is burned by strategy S in G. If u ∈ J then it will be burned by S 0
in H. If u ∈ C \ J and no vertex of J burned by S in G then there exists burned
vertex x ∈ XH . Since |N(x) ∩ C 0 | > l + 1, at least one vertex of K gets burned. t
u
Claim 1 If a strategy S saves at least 2l + 1 vertices in G then S saves entire
clique.
Proof. Let S be a valid strategy which saves at least 2l + 1 vertices in G. Suppose
assume that there exists a vertex v ∈ C burned by strategy S, then no vertex in
C is saved except the defended vertices. The strategy S can save at most l − 1
vertices in X and l + 1 vertices in C, total S saves at most 2l vertices which is a
contradiction to the fact that S saves at least 2l + 1 vertices.
t
u
Claim 2 Saving one undefended vertex in C is equivalent to saving entire clique.
Proof. Let v be an undefended saved vertex of C. If any vertex of C is burned
by S then v gets burned contradicting the fact that v is a saved vertex.
t
u
Lemma 9. Let G be a graph and H be the graph obtained after applying reduction rules. A strategy S saves at least k vertices in G if and only if there exists
a strategy S 0 that saves at least k 0 vertices in H.
Proof. Let S be any valid strategy on G then we can find a corresponding strategy
S 0 on H as follows. If S defends a vertex v in C \ J which is deleted in reduction
procedure, then by Remark 1 instead of v we can defend any other non-defended
vertex in L. Since S can defend at most l + 1 vertices in G and |L| = l + 1, we can
always replace vertices of C \ J in S by applying Remark 1.
Conversely, let S 0 be any valid strategy on H then we can find its corresponding strategy S on G as follows. If S 0 defends a vertex v in K ∪ L which is added
in reduction procedure, then by Remark 1 instead of v we can defend any other
non-defended vertex in C \ J. Since S 0 can defend at most l + 1 vertices in H and
|C \ J| > 2l + 3, we can always replace vertices of K ∪ J in S 0 by applying Remark 1.
The parameter k 0 is defined as follows.
15

1. If k ∈ [|C|, |C| + l − 1], then set k 0 = k − |C| + |J| + |K| + |L| 6 l2 + 4l + 3.
2. If k ∈ [2l + 1, |C| − 1], then set k 0 = 2l + 1.
3. If k ∈ [1, 2l], then set k 0 = k.
Using Lemma 8, Claims 1 and 2 we can see that the strategy S saves at least
k vertices in G if and only if the strategy S 0 saves at least k 0 vertices in H.
t
u
4.2

Parameterization by Distance to Stars

In this section, we show that Saving k-Vertices does not admit a polynomial
kernel parameterized by distance to stars unless NP ⊆ coNP/poly. First we
introduce a notion of polynomial time and parameter transformation, that under
the assumption NP * coNP/poly allows us to show non-existence of polynomial
kernels.
Definition 2. [3] Let P and Q be parameterized problems, we say that there is
a polynomial-parameter transformation from P to Q, denoted P 6ppt Q, if there
exists a polynomial time computable function f : {0, 1}∗ × N → {0, 1}∗ × N and
polynomial p : N → N, for all x ∈ {0, 1}∗ and k ∈ N, then following hold
1. (x, k) ∈ P if and only if (x 0 , k 0 ) = f(x, k) ∈ Q
2. k 0 6 p(k)
The function f is called a polynomial-parameter transformation from P to Q.
Theorem 5. [3] Let P and Q be parameterized problems, and suppose that Pc
and Qc are the derived classical problems. Suppose that Pc is NP-complete, and
Qc ∈ NP. Suppose that f is a polynomial time and parameter transformation from
P to Q. Then, if Q has a polynomial kernel, then P has a polynomial kernel.
Corollary 6. Let P and Q be parameterized problems whose unparameterized
versions Pc and Qc are NP-complete. If P 6ppt Q and P does not have a polynomial kernel, then Q does not have a polynomial kernel.

Clique [Vertex Cover]
Input: A graph G, a vertex cover X ⊆ V(G) and an integer
k.
Parameter: The size l := |X| of the vertex cover.
Question: Does there exists a clique of size k in G?

Theorem 6. [2] Clique [Vertex Cover] does not admit a polynomial kernel
unless NP ⊆ coNP/poly.
Theorem 7. Saving k-Vertices parameterized by the distance to disjoint union
of stars does not admit a polynomial kernel, unless NP ⊆ coNP/poly.
16

V

D
d11

X
d21

J
J24

2
J23

3
4

J34
2

4

1

5

s

d12

3

d22

J12
1

G

J45
d13

5

d23

H

I

Fig. 3 An instance of Clique [Vertex Cover] and the constructed graph H
represents Saving k-Vertices [Distance to stars] in the proof of Theorem 7 for
l = 2 and k = 3. In this example X = {2, 4} is a vertex cover of G and H\({s}∪D∪X)
is disjoint union of stars (graph induced by blue vertices).

Proof. We show that there is a polynomial-parameter transformation from Clique
[Vertex Cover] to Saving k-Vertices [Distance to stars]. Let (G, X, l, k) be
an instance of Clique [Vertex Cover]. We construct a graph H (see Fig. 3)
from G as follows. Initialize H as a copy of G, this set of vertices are denoted by
V = X ∪ I For each edge uv ∈ E(G) add a vertex Juv to H and make it adjacent
to both vertices u and v. we denote this set of vertices with J.
Add a root vertex s, and add vertices dij (set of vertices denoted by D) for
1 6 i 6 k − 1 and 1 6 j 6 k. Add edges between dij to di 0 j 0 for all i, j, j 0 and
i 0 = i + 1. Connect s to d1,j for all j and connect dk−1,j to each vertex of G
in H for all j. Vertex set of H is V(H) = {s} ∪ D ∪ V ∪ J. It is easy to see that
H \ ({s} ∪ D ∪ X) is a disjoint union of stars. Therefore H is k(k − 1) + l + 1 distance
to stars with X 0 = {s} ∪ D ∪ X as a modulator. Since k 6 l + 1, H is at most (l + 1)2
distance to stars. Let l 0 := |X 0 | is polynomially bounded in the input parameter

l and we can construct the graph H in polynomial time. Set k 0 = k + k2 + 1 for
saving vertices in H. Let (H, X 0 , l 0 , k 0 ) is an instance of the Saving k-Vertices
problem parameterized by a distance to stars.
We show that Saving k-Vertices on (H, X 0 , l 0 , k 0 ) is a yes instance if and
only if there is a k-clique on (G, X, l,1k) is a yes instance. Suppose that (G, X, l, k)
is a yes-instance of Clique [Vertex Cover] and C be a k-clique in G. We can
find a valid strategy S which saves at least k 0 vertices in H as follows: For first
k time steps S defends k vertices of C in H. At time step k + 1, S defends some
vertex Juv in H such that uv 6∈ E(C). The strategy S saves k vertices in C and
saves k2 vertices in H corresponding to clique edges in G and the vertex Juv .
Conversely, suppose that S is a valid strategy that saves at least k 0 vertices
in H. It is easy to see that at any time step, defending a vertex dij for any
i, j is not helpful, because there is at least one burning vertex di,j 0 with same
neighborhood as dij . Further protecting Juv vertices for some uv ∈ E(G) does
not
 save any vertices. So the vertices in S ∩ V are responsible for saving at least
k
2 many vertices.
17


If |S ∩ I| = d > 2 then in the best case S can save at most k 00 = k + 1 + k−d
+
2
d(k − d) = k + 1 + (k − d)(k + d − 1)/2 vertices in H. Observe that k 00 is less than
k 0 for d > 2, contradiction to fact that the strategy S saves at least k 0 vertices
in H. Therefore |S ∩ I| 6 1. If S ∩ I = ∅ then the strategy S saves at least k 0
vertices if and only if the vertices defended in S ∩ X are forms a k-clique in G.
If |S ∩ I| = 1 then S defends one vertex v in I and k − 1 vertices in X. S saves at
least k 0 vertices if k − 1 vertices defended in X induces a (k − 1)-clique in G and v
is adjacent to k − 1 defended vertices. Combining both cases, S can save at least
k 0 vertices in H if the vertices defended in S ∩ V forms a k-clique in G.
t
u

5

Conclusion

In this paper, we studied the parameterized complexity of Firefighting problem for various structural parameters. We considered the size of a modulator
to threshold graphs, cluster graphs and disjoint unions of stars as parameters,
and showed FPT algorithms in all cases. We also established that Firefighting
admits a polynomial kernel when parameterized by the size of a modulator to a
clique, while it is unlikely to admit a polynomial kernel when parameterized by
the size of a modulator to a disjoint union of stars. In contrast to the tractability
results, we found that Firefighting is W[1]-hard when parameterized by the
distance to split graphs.
The following problems remain open. Does Saving k-Vertices admit a
polynomial kernel when parameterized by k and the size of a vertex cover? Also,
is the Firefighting problem FPT when parameterized by distance to cographs?

References
1. Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen,
E.J.: Parameterized complexity of firefighting. Journal of Computer and System
Sciences 80(7), 1285–1297 (2014)
2. Bodlaender, H.L., Jansen, B.M., Kratsch, S.: Kernelization lower bounds by crosscomposition. SIAM Journal on Discrete Mathematics 28(1), 277–305 (2014)
3. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and
disjoint paths. Theoretical Computer Science 412(35), 4570–4578 (2011)
4. Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary
properties. Information Processing Letters 58(4), 171–176 (1996)
5. Cai, L., Verbin, E., Yang, L.: Firefighting on trees:(1- 1/e)–approximation, fixed
parameter tractability and a subexponential algorithm. In: International Symposium on Algorithms and Computation. pp. 258–269. Springer (2008)
6. Chalermsook, P., Chuzhoy, J.: Resource minimization for fire containment. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms.
pp. 1334–1349. Society for Industrial and Applied Mathematics (2010)
7. Chlebı́ková, J., Chopin, M.: The firefighter problem: Further steps in understanding
its complexity. Theoretical Computer Science 676, 42–51 (2017)
8. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M.,
Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 4. Springer (2015)

18

9. Downey, R.G., Fellows, M.R.: Parameterized complexity, vol. 3. springer Heidelberg
(1999)
10. Finbow, S., Hartnell, B., Li, Q., Schmeisser, K.: On minimizing the effects of fire
or a virus on a network. Journal of Combinatorial Mathematics and Combinatorial
Computing 33, 311–322 (2000)
11. Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs
of maximum degree three. Discrete Mathematics 307(16), 2094–2105 (2007)
12. Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions
and questions. The Australasian Journal of Combinatorics 43, 57–77 (2009)
13. Foldes, S., Hammer, P.L.: Split graphs. Universität Bonn. Institut für Ökonometrie
und Operations Research (1976)
14. Fomin, F.V., Heggernes, P., van Leeuwen, E.J.: The firefighter problem on graph
classes. Theoretical Computer Science 613, 38–50 (2016)
15. Ganian, R.: Improving vertex cover as a graph parameter. Discrete Mathematics
& Theoretical Computer Science 17(2), 77–100 (2015)
16. Hartnell, B.: Firefighter! an application of domination. In: 25th Manitoba Conference on Combinatorial Mathematics and Computing (1995)
17. King, A., MacGillivray, G.: The firefighter problem for cubic graphs. Discrete
Mathematics 310(3), 614–621 (2010)
18. Leung, M.L.: Fixed parameter tractable algorithm for firefighting problem. arXiv
preprint arXiv:1104.1044 (2011)
19. MacGillivray, G., Wang, P.: On the firefighter problem. Journal of Combinatorial
Mathematics and Combinatorial Computing 47, 83–96 (2003)

19

