New Integrality Gap Results for the Firefighters Problem on
Trees
Parinya Chalermsook1 and Daniel Vaz1,2
1

arXiv:1601.02388v3 [cs.DM] 29 Jul 2016

2

Max-Planck-Institut für Informatik, Saarbrücken, Germany
Graduate School of Computer Science, Saarland University, Saarbrücken, Germany
{parinya, ramosvaz}@mpi-inf.mpg.de
1st August 2016

Abstract
In the firefighter problem on trees, we are given a tree G = (V, E) together with a vertex
s ∈ V where the fire starts spreading. At each time step, the firefighters can pick one vertex
while the fire spreads from burning vertices to all their neighbors that have not been picked.
The process stops when the fire can no longer spread. The objective is to find a strategy
that maximizes the total number of vertices that do not burn. This is a simple mathematical
model, introduced in 1995, that abstracts the spreading nature of, for instance, fire, viruses,
and ideas. The firefighter problem is NP-hard and admits a (1 − 1/e) approximation based
on rounding the canonical LP. Recently, a PTAS was announced[1]. 1
The goal of this paper is to develop better understanding on the power of LP relaxations
for the firefighter problem. We first show a matching lower bound of (1 − 1/e + ) on the
integrality gap of the canonical LP. This result relies on a powerful combinatorial gadget that
can be used to derive integrality gap results in other related settings. Next, we consider the
canonical LP augmented with simple additional constraints (as suggested by Hartke). We
provide several evidences that these constraints improve the integrality gap of the canonical
LP: (i) Extreme points of the new LP are integral for some known tractable instances and
(ii) A natural family of instances that are bad for the canonical LP admits an improved
approximation algorithm via the new LP. We conclude by presenting a 5/6 integrality gap
instance for the new LP.

1

Introduction

Consider the following graph-theoretic model that abstracts the fire spreading process: We are
given graph G = (V, E) together with the source vertex s where the fire starts. At each time
step, we are allowed to pick some vertices in the graph to be saved, and the fire spreads from
burning vertices to their neighbors that have not been saved so far. The process terminates
when the fire cannot spread any further. This model was introduced in 1995 [13] and has been
used extensively by researchers in several fields as an abstraction of epidemic propagation.
There are two important variants of the firefighters problem. (i) In the maximization variant
(Max-FF), we are given graph G and source s, and we are allowed to pick one vertex per time
step. The objective is to maximize the number of vertices that do not burn. And (ii) In
the minimization variant (Min-FF), we are given a graph G, a source s, and a terminal set
1

The (1 − 1/e) approximation remained the best until very recently when Adjiashvili et al. [1] showed a PTAS.
Their PTAS does not bound the LP gap.

1

X ⊆ V (G), and we are allowed to pick b vertices per time step. The goal is to save all terminals
in X , while minimizing the budget b.
In this paper, we focus on the Max-FF problem. The problem is n1− hard to approximate
in general graphs [2], so there is no hope to obtain any reasonable approximation guarantee.
Past research, however, has focused on sparse graphs such as trees or grids. Much better
approximation algorithms are known on trees: The problem is NP-hard [15] even on trees of
degree at most three, but it admits a (1 − 1/e) approximation algorithm. For more than a
decade [2, 6, 5, 10, 14, 15], there was no progress on this approximability status of this problem,
until a PTAS was recently discovered [1].
Besides the motivation of studying epidemic propagation, the firefighter problem and its
variants are interesting due to their connections to other classical optimization problems:
• (Set cover) The firefighter problem is a special case of the maximum coverage problem with
group budget constraint (MCG) [7]: Given a collection of sets S = {S1 , . . . , Sm } : Si ⊆ X,
together with group constraints, i.e. a partition of S into groups G1 , . . . , G` , we are
interested in choosing one set from each group in a way that maximizes the total number
of elements covered, i.e. a feasible solution is a subset S 0 ⊆ S where |S 0 ∩ Gj | ≤ 1 for all j,
S
and | Si ∈S 0 Si | is maximized. It is not hard to see that Max-FF is a special case of MCG.
We refer the readers to the discussion by Chekuri and Kumar [7] for more applications of
MCG.
• (Cut) In a standard minimum node-cut problem, we are given a graph G together with
a source-sink pair s, t ∈ V (G). Our goal is to find a collection of nodes V 0 ⊆ V (G) such
that G \ V 0 has s and t in distinct connected components. Anshelevich et al. [2] discussed
that the firefighters’ solution can be seen as a “cut-over-time” in which the cut must be
produced gradually over many timesteps. That is, in each time step t, the algorithm is
allowed to choose vertex set Vt0 to remove from the graph G, and again the final goal
is to “disconnect” s from t 2 . This cut-over-time problem is exactly equivalent to the
minimization variant of the firefighter problem. We refer to [2] for more details about this
equivalence.

1.1

Our Contributions

In this paper, we are interested in developing a better understanding of the Max-FF problem
from the perspective of LP relaxation. The canonical LP relaxation has been used to obtain
the known (1 − 1/e) approximation algorithm via straightforward independent LP rounding
(each node is picked independently with the probability proportional to its LP-value). So far, it
was not clear whether an improvement was possible via this LP, for instance, via sophisticated
dependent rounding schemes 3 . Indeed, for the corresponding minimization variant, Min-FF,
Chalermsook and Chuzhoy designed a dependent rounding scheme for the canonical LP in
order to obtain O(log∗ n) approximation algorithm, improving upon an O(log n) approximation
obtained via independent LP rounding. In this paper, we are interested in studying this potential
improvement for Max-FF.
Our first result refutes such possibility for Max-FF. In particular, we show that the integrality gap of the standard LP relaxation can be arbitrarily close to (1 − 1/e).
Theorem 1. For any  > 0, there is an instance (G, s) (whose size depends on ) such that the
ratio between optimal integral solution and fractional one is at most (1 − 1/e + ).
2

The notion of disconnecting the vertices here is slightly non-standard.
Cai, Verbin, and Yang [5] claimed an LP-respecting integrality gap of (1 − 1/e), but many natural rounding
algorithms in the context of this problem are not LP respecting, e.g. in [6]
3

2

Our techniques rely on a powerful combinatorial gadget that can be used to prove integrality
gap results in some other settings studied in the literature. In particular, in the b-Max-FF
problem, the firefighters can pick up to b vertices per time step, and the goal is to maximize the
number of saved vertices. We provide an integrality gap of (1 − 1/e) for the b-Max-FF problem
for all constant b ∈ N, thus matching the algorithmic result of [9]. In the setting where
√ an input
tree has degree at most d ∈ [4, ∞), we show an integrality gap result of (1−1/e+O(1/ d)). The
best known algorithmic result in this setting was previously a (1 − 1/e + Ω(1/d)) approximation
due to [14].
Motivated by the aforementioned negative results, we search for a stronger LP relaxation for
the problem. We consider adding a set of valid linear inequalities, as suggested by Hartke [12].
We show the following evidences that the new LP is a stronger relaxation than the canonical
LP.
• Any extreme point of the new LP is integral for the tractable instances studied by Finbow
et al. [11]. In contrast, we argue that the canonical LP does not satisfy this integrality
property of extreme points.
• A family of instances which captures the bad integrality gap instances given in Theorem 1,
admits a better than (1 − 1/e) approximation algorithm via the new LP.
• When the LP solution is near-integral, e.g. for half-integral solutions, the new LP is
provably better than the old one.
Our results are the first rigorous evidences that Hartke’s constraints lead to improvements
upon the canonical LP. All the aforementioned algorithmic results exploit the new LP constraints
in dependent LP rounding procedures. In particular, we propose a two-phase dependent rounding algorithm, which can be used in deriving the second and third results. We believe the new
LP has an integrality gap strictly better than (1 − 1/e), but we are unable to analyze it.
Finally, we show a limitation of the new LP by presenting a family of instances, whose
integrality gap can be arbitrarily close to 5/6. This improves the known integrality gap ratio [12],
and puts the integrality gap answer somewhere between (1 − 1/e) and 5/6. Closing this gap is,
in our opinion, an interesting open question.
Organization: In Section 2, we formally define the problem and present the LP relaxation.
In Section 3, we present the bad integrality gap instances. We present the LP augmented with
Hartke’s constraints in Section 4 and discuss the relevant evidences of its power in comparison to
the canonical LP. Some proofs are omitted for space constraint, and are presented in Appendix.
Related results: King and MacGillivray showed that the firefighter problem on trees is
solvable in polynomial time if the input tree has degree at most three, with the fire starting
at
√
a degree-2 vertex. From exponential time algorithm’s perspective, Cai et al. showed 2O( n log n)
time, exact algorithm. The discrete mathematics community pays particularly high attention
to the firefighter problem on grids [16, 10], and there has also been some work on infinite
graphs [13].
The problem also received a lot of attention from the parameterized complexity perspectives [8, 3, 5] and on many special cases, e.g., when the tree has bounded pathwidth [8] and on
bounded degree graphs [8, 4].
Recent update: Very recently, Adjiashvili et al. [1] showed a polynomial time approximation scheme (PTAS) for the Max-FF problem, therefore settling the approximability status.
Their results, however, do not bound the LP integrality gap. We believe that the integrality
gap questions are interesting despite the known approximation guarantees.

3

2

Preliminaries

A formal definition of the problem is as follows. We are given a graph G and a source vertex s
where the fire starts spreading. A strategy is described by a collection of vertices U = {ut }nt=1
where ut ∈ V (G) is the vertex picked by firefighters at time t. We say that a vertex u ∈ V (G)
is saved by the strategy U if for all path P = (s = v0 , . . . , vz = u) from s to u, we have
vi ∈ {u1 , . . . , ui } for some i = 1, . . . , z. A vertex v not saved by U is said to be a burning vertex.
The objective of the problem is to compute U so as to maximize the total number of saved
vertices. Denote by OPT(G, s) the number of vertices saved by an optimal solution.
When G is a tree, we think of G as being partitioned into layers L1 , . . . , Lλ where λ is the
height of the tree, and Li contains vertices whose distance is exactly i from s. Every strategy
has the following structure.
Proposition 2. Consider the firefighters problem’s instance (G, s) where G is a tree. Let
U = {u1 , . . . , un } be any strategy. Then there is another strategy U 0 = {u0t } where u0t belongs to
layer t in G, and U 0 saves at least as many vertices as U does.
We remark that this structural result only holds when an input graph G is a tree.
LP Relaxation: This paper focuses on the linear programming aspect of the problem. For
any vertex v, let Pv denote the (unique) path from s to v, and let Tv denote the subtree rooted
at v. A natural LP relaxation is denoted by (LP-1): We have variable xv indicating whether v
is picked by the solution, and yv indicating whether v is saved.
(LP-2)

(LP-1)
max

X

max

yv
xv ≤ 1 for all layer j

X

xv ≤ 1 for all layer j

v∈Lj

v∈Lj

yv ≤

yv

v∈X

v∈V

X

X

X

xu for all v ∈ V

yv ≤

X

xu for all v ∈ X

u∈Pv

u∈Pv

xv , yv ∈ [0, 1] for all v

xv , yv ∈ [0, 1] for all v

Let LP(T, s) denote the optimal fractional LP value for an instance (T, s). The integrality
gap gap(T, s) of the instance (T, s) is defined as gap(T, s) = OPT(T, s)/LP(T, s). The integrality
gap of the LP is defined as inf T gap(T, s).
Firefighters with terminals: We consider a more general variant of the problem, where
we are only interested in saving a subset X of vertices, which we call terminals. The goal is
now to maximize the number of saved terminals. An LP formulation of this problem, given an
instance (T, v, X ), is denoted by (LP-2). The following lemma argues that these two variants
are “equivalent” from the perspectives of LP relaxation.
Lemma 3. Let (T, X , s), with |X | > 0, be an input for the terminal firefighters problem that
gives an integrality gap of γ for (LP-2), and that the value of the fractional optimal solution is
at least 1. Then, for any  > 0, there is an instance (T 0 , s0 ) that gives an integrality gap of γ + 
for (LP-1).
Proof. Let M = 2|V (T )|/. Starting from (T, X , s), we construct an instance (T 0 , s0 ) by adding
M children to each vertex in X , so the number of vertices in T 0 is |V (T 0 )| = |V (T )| + M |X |.
We denote the copies of X in T 0 by X 0 and the set of their added children by X 00 . The root of
4

the new tree, s0 , is the same as s (the root of T .) Now we argue that the instance (T 0 , s0 ) has
the desired integrality gap, i.e. we argue that OPT(T 0 , s0 ) ≤ (γ + )LP(T 0 , s0 ).
Let (x0 , y 0 ) be an integral solution to the instance (T 0 , s0 ). We upper bound the number of
P
vertices saved by this solution, i.e. upper bounding v∈V (T 0 ) yv0 . We analyze three cases:
• For a vertex v ∈ V (T 0 ) \ X 00 , we upper bound the term yv0 by 1, and so the sum
P
0
v∈V (T 0 )\X 00 yv by |V (T )|.
• Now define X̃ ⊆ X 00 as the set of vertices v for which yv0 = 1 but yu0 = 0 for the parent u of
P
0 ≤ |X |: We break the
v. This means
that x0v = 1 for all vertices
in X̃ . Notice that v∈X̃ yvo
n o
n
set X̃ into X̃u

where X̃u = v ∈ X̃ : u is the parent of v . The LP constraint

u∈V (T 0 )
P
P
guarantees that v∈X̃u yv0 = v∈X̃u x0v ≤ 1 (all vertices in X̃u belong to the same layer.)

Summing over all such u ∈ X 0 , we get the desired bound.

• Finally, consider the term v∈X 0 \X̃ yv0 . Let (x∗ , y ∗ ) be an optimal fractional solution
to (T, X , s) for (LP-2). We only need to care about all vertices v such that yu0 = 1
P
for the parent u of v. This term is upper bounded by M u∈X 0 yu0 , which is at most
P
M γ ( v∈X yv∗ ), due to the fact that the solution (x0 , y 0 ) induces an integral solution on
instance (T, X , s).
P

Combining the three cases, we get |V (T )| + |X | + M γ ( v∈X yv∗ ) ≤ M + γM ( v∈X yv∗ ) ≤
P
P
M (γ + ) ( v∈X yv∗ ), if v∈X yv∗ ≥ 1. Now, notice that the fractional solution (x∗ , y ∗ ) for (LP-2)
on instance (T, X , s) is also feasible for (LP-1) on (T 0 , s0 ) with at least a multiplicative factor
of M times the objective value: Each fractional saving of u ∈ X 0 contributes to save all M
P
children of u. Therefore, M ( v∈X yv∗ ) ≤ M · LP(T 0 , s0 ), thus concluding the proof.
P

P

We will, from now on, focus on studying the integrality gap of (LP-2).

3

Integrality Gap of (LP-2)

We first discuss the integrality gap of (LP-2) for a general tree. We use the following combinatorial gadget.
Gadget: A (M, k, δ)-good gadget is a collection of trees T = {T1 , . . . , TM }, with roots
S
r1 , . . . , rM where ri is a root of Ti , and a subset S ⊆ V (Ti ) that satisfy the following properties:
• (Uniform depth) We think of these trees as having layers L0 , L1 , . . . , Lh , where Lj is the
union over all trees of all vertices at layer j and L0 = {r1 , . . . , rm }. All leaves are in the
same layer Lh .
• (LP-friendly) For any layer Lj , j ≥ 1, we have |S ∩ Lj | ≤ k. Moreover, for any tree Ti
and a leaf v ∈ V (Ti ), the unique path from ri to v must contain at least one vertex in S.
• (Integrally adversarial) Let B ⊆ {r1 , . . . , rM } be any subset of roots. Consider a subset of
vertices U = {uj }hj=1 such that uj ∈ Lj . For ri ∈ B and a leaf v ∈ Lh ∩ V (Ti ), we say that
v is (U, B)-risky if the unique path from ri to v does not contain any vertex in U. There
must be at least (1 − 1/k − δ) |B|
M |Lh | vertices in Lh that are (U, B)-risky, for all choices of
B and U.
We say that vertices in S are special and all other vertices are regular.

5

Lemma 4. For any integers k ≥ 2, M ≥ 1, and any real number δ > 0, a (M, k, δ)-good gadget
exists. Moreover, the gadget contains at most (k/δ)O(M ) vertices.
We first show how to use this lemma to derive our final construction. The proof of the
lemma follows later.
Construction: Our construction proceeds in k phases, and we will define it inductively.
The first phase of the construction is simply a (1, k, δ)-good gadget. Now, assume that we
have constructed the instance up to phase q. Let l1 , . . . , lMq ∈ Lαp be the leaves after the
construction of phase q that all lie in layer αq . In phase q + 1, we take the (Mq , k, δ)-good
gadget (Tq , {rq }, Sq ); recall that such a gadget consists of Mq trees. For each i = 1, . . . , Mq , we
unify each root ri with the leaf li . This completes the description of the construction.
S
Denote by S̄q = q0 ≤q Sq0 the set of all special vertices in the first q phases. After phase q,
we argue that our construction satisfies the following properties:
• All leaves are in the same layer αq .
• For every layer Lj , |Lj ∩ S̄q | ≤ k. For every path P from the root to v ∈ Lαi , |P ∩ S̄q | = q.
• For any integral solution U, at least |Lαq | ((1 − 1/k)q − qδ) vertices of Lαq burn.
It is clear from the construction that the leaves after phase q are all in the same layer. As
to the second property, the properties of the gadget ensure that there are at most k special
vertices per layer. Moreover, consider each path P from the root to some vertex v ∈ Lαq+1 . We
can split this path into two parts P = P 0 ∪ P 00 where P 0 starts from the root and ends at some
v 0 ∈ Lαq , and P 00 starts at v 0 and ends at v. By the induction hypothesis, |P 0 ∩ S̄q | = q and the
second property of the gadget guarantees that |P 00 ∩ Sq+1 | = 1.
To prove the final property, consider a solution U = {u1 , . . . , uαq+1 }, which can be seen as
0
U ∪ U 00 where U 0 = {u1 , . . . , uαq } and U 00 = {uαq +1 , . . . , uαq+1 }. By the induction hypothesis,
we have that at least ((1 − 1/k)q − qδ) |Lαq | vertices in Lαq burn; denote these burning vertices
|B|
by B. The third property of the gadget will ensure that at least (1 − 1/k − δ) M
|Lαq+1 | vertices
q
00
in Lαq+1 must be (U , B)-risky. For each risky vertex v ∈ Lαq+1 , a unique path from the root
to v 0 ∈ B does not contain any vertex in U 0 , and also the path from v 0 to v does not contain a
vertex in U 00 (due to the fact that it is (U 00 , B)-risky.) This implies that such vertex v must burn.
Therefore, the fraction of burning vertices in layer Lαq+1 is at least (1 − 1/k − δ)|B|/Mq ≥ (1 −
1/k −δ)((1−1/k)q −qδ), by induction hypothesis. This number is at least (1−1/k)q+1 −(q +1)δ,
maintaining the invariant.
After the construction of all k phases, the leaves are designated as the terminals X . Also,
Mq+1 ≤ (k/δ)2Mq , which means that, after k phases, Mk is at most a tower function of (k/δ)2 ,
···
that is, (k/δ)2(k/δ) with k − 1 such exponentiations. The total size of the construction is
P
2Mq ≤ (k/δ)2Mk = O(M
k+1 ).
q (k/δ)
An example construction, when k = 2, is presented in Figure 3 (in Appendix).
Theorem 5. A fractional solution, that assigns xv = 1/k to each special vertex v, saves every
terminal. On the other hand, any integral solution can save at most a fraction of 1−(1−1/k)k +.
Proof. We assign the LP solution xv = 1/k to all special vertices (those vertices in S̄k ), and
xv = 0 to regular vertices. Since the construction ensures that there are at most k special vertices
P
per layer, we have v∈Lj xv ≤ 1 for every layer Lj . Moreover, every terminal is fractionally
P
saved: For any t ∈ X , the path |Pt ∩ S̄k | = k, so we have v∈Pt xv = 1.
For the integral solution analysis, set δ = /k. The proof follows immediately from the
properties of the instance.
6

3.1

Proof of Lemma 4

We now show that the (M, k, δ)-good gadget exists for any value of M ∈ N, k ∈ N, k ≥ 2 and
δ ∈ R>0 . We first describe the construction and then show that it has the desired properties.
Construction: Throughout the construction, we use a structure which we call spider. A
spider is a tree in which every node except the root has at most one child. If a node has no
children (i. e. a leaf), we call it a foot of the spider. We call the paths from the root to each
foot the legs of the spider.
Let D = d4/δe. For each i = 1, . . . , M , the tree Ti is constructed as follows. We have a
spider rooted at ri that contains kDi−1 legs. Its feet are in Di−1 consecutive layers, starting at
P
layer αi = 1 + j<i Dj−1 ; each such layer has k feet. Denote by S (i) the feet of these spiders.
Next, for each vertex v ∈ S (i) , we have a spider rooted at v, having D2M −i+1 feet, all of which
P
S
(i)
belong to layer α = 1 + j≤M Dj−1 . The set S is defined as S = M
i=1 S . This concludes the
construction. We will use the following observation:
Observation 6. For each root ri , the number of leaves of Ti is kD2M .
Analysis: We now prove that the above gadget is (M, k, δ)-good. The construction ensures
that all leaves are in the same layer Lα .
The second property also follows obviously from the construction: For i 6= i0 , we have that
0
(i)
S ∩ S (i ) = ∅, and that each layer contains exactly k vertices from S (i) . Moreover, any path
from ri to the leaf of Ti must go through a vertex in S (i) .
The third and final property is established by the following two lemmas.
Lemma 7. For any ri ∈ B and any subset of vertices U = {uj }hj=1 such that uj ∈ Lj , a fraction
of at least (1 − 1/k − 2/D) of S (i) are (U, B)-risky.
Proof. Notice that a vertex v is (U, B)-risky if U is not a vertex cut separating v from B. There
are kDi−1 vertex-disjoint paths from ri ∈ B to vertices in S (i) . But the cut U induced on these
P
0
paths contains at most i0 ≤i Di −1 vertices (because all vertices in S (i) are contained in the
P
0
first i0 ≤i Di −1 ≤ Di−1 + 2Di−2 layers.) Therefore, at most (1/k + 2/D) fraction of vertices in
S (i) can be disconnected by U, and those that are not cut remain (U, B)-risky.
Lemma 8. Let v ∈ S (i) that is (U, B)-risky. Then at least (1 − 2/D) fraction of descendants
of v in Lα must be (U, B)-risky.
Proof. Consider each v ∈ S (i) that is (U, B)-risky and a collection of leaves Lv that are descendants of vertex v. Notice that a leaf u ∈ Lv is (U, B)-risky if removing U does not disconnect
vertex v from u.
There are D2M −i+1 ≥ DM +1 vertex disjoint paths connecting vertex v with leaves in Lv ,
while the cut set U contains at most 2DM vertices. Therefore, removing U can disconnect at
most 2/D fraction of vertices in Lv from v.
Combining the above two lemmas, for each ri ∈ B, the fraction of leaves of Ti that are
(U, B)-risky are at least (1 − 1/k − 2/D)(1 − 2/D) ≥ (1 − 1/k − 4/D). Therefore, the total
number of such leaves, over all trees in T , are (1 − 1/k − δ)|B||Lα |/M .
We extend the cosntruction to other settings in Section 3.1 (in Appendix).
Arbitrary number of firefighters: Let b ∈ N. In the b-firefighter problem, at each time
step, the firefighters may choose up to b vertices, and the fire spreads from the burning vertices
to vertices that have not been chosen so far. The goal is to maximize the number of saved
vertices. In this section, we show the following:

7

Theorem 9. For any integer b ∈ N (independent of |V (G)|), the integrality gap of the canonical
LP can be arbitrarily close to (1 − 1/e).
Proof. To prove this theorem, one only need to design a slightly different good gadget. That
is, an (M, k, δ)-good gadget is now a collection of trees T with roots r1 , . . . , rM together with
S
S ⊆ V (Ti ) that satisfy the following properties:
• All leaves of Ti are in the same layer Lh .
• For each layer Lj , we have |S ∩ Lj | ≤ kb. Moreover, for any tree Ti and a leaf v ∈ V (Ti ),
the unique path from ri to v must contain at least one vertex in S.
h|
• For any subset B ⊆ {r1 , . . . , rM } of roots and for any strategy U, at least (1−1/k−δ) |B||L
M
vertices in Lh are (U, B)-risky.

It is not hard to see that these gadgets can be used to construct the integrality gap in the
same way as in the previous section. Details are omitted.
Bounded degrees: Iwakawa et al. showed a (1 − 1/e + Ω(1/d)) approximation algorithm for
the instance that has degree at most d. We show an instance where this dependence on 1/d is
almost the best possible that can be obtained from this LP.
Theorem
10. For all d ≥ 4, the integrality gap of (LP-1) on degree-d graphs is (1 − 1/e +
√
O(1/ d)).
Proof. To prove this theorem, we construct a “bounded degree” analogue of our good gadgets.
That is, the (M, k)-good gadget in this setting guarantees that
• All leaves of Ti are in the same layer Lh .
• For each layer Lj , we have |S ∩ Lj | ≤ k. For each tree Ti , for each leaf v ∈ V (Ti ), the
unique path from ri to v contains one vertex in S.
h|
• For any subset B ⊆ {r1 , . . . , rM }, for any strategy U, at least (1 − 1/k − O(1/d)) |B||L
M
vertices in Lh are (U, B)-risky.

This gadget can be used to recursively construct the instance in k phases.
The final instance
√
k
guarantees the integrality
√ gap of 1−(1−1/k) +O(k/d). By setting k = d, we get the integrality
gap of (1 − 1/e + O(1/ d)) as desired4 .

4

Hartke’s Constraints

Due to the integrality gap result in the previous section, there is no hope to improve the best
known algorithms via the canonical LP relaxation. Hartke [12] suggested adding the following
constraints to narrow down the integrality gap of the LP.
X

xu ≤ 1 for all vertex v ∈ V (T ) and layer Lj below the layer of v

u∈Pv ∪(Tv ∩Lj )

We write the new LP with these constraints below:
4

By analyzing the Taylor’s series expansion of 1/e − (1 − 1/k)k , we get the term

8

1
2ek

+ O(1/k2 )

(LP’)
max

X

yv

v∈V

xu ≤ 1 for all layer j below vertex v

X
u∈Pv ∪(Tv ∩Lj )

yv ≤

X

xu for all v ∈ V

u∈Pv

xv , yv ∈ [0, 1] for all v
Proposition 11. Given the values {xv }v∈V (T ) that satisfy the first set of constraints, then the
P
solution (x, y) defined by yv = u∈Pv xv is feasible for (LP’) and at least as good as any other
feasible (x, y 0 ).
In this section, we study the power of this LP and provide three evidences that it may be
stronger than (LP-1).

4.1

New properties of extreme points

In this section, we show that Finbow et al. tractable instances [11] admit a polynomial time
exact algorithm via (LP’) (in fact, any optimal extreme point for (LP’) is integral.) In contrast,
we show that (LP-1) contains an extreme point that is not integral.
We first present the following structural lemma.
Lemma 12. Let (x, y) be an optimal extreme point for (LP’) on instance T rooted at s. Suppose
s has two children, denoted by a and b. Then xa , xb ∈ {0, 1}.
Proof. Suppose that xa , xb ∈ (0, 1). We will define two solutions (x0 , y0 ) and (x00 , y00 ) and derive
that (x, y) can be written as a convex combination of (x0 , y0 ) and (x00 , y00 ), a contradiction.
First, we define (x0 , y0 ) by setting x0b = 1, x0a = 0. For each vertex v ∈ Tb , we set x0v = 0. For
each vertex v ∈ Ta , we define x0v = xv /(1 − xa ). We verify that x0 is feasible
for (LP’):
For each
P

v ∈ Ta and any layer Lj below v,

0
u∈Pv xu

P

+

0
u∈Tv ∩Lj xu

P

=

P

xu −xa
(1−xa )

u∈Pv

+

u∈Tv ∩Lj

xu

(1−xa )

≤



P
u∈Pv ∪(Tv ∩Lj )

xu −xa

≤ 1 (the last inequality is due to the fact that x is feasible). The
P
constraint is obviously satisfied for all v ∈ Tb . For the root node v = s, we have u∈Lj x0u =
(1−xa )

P



u ∈(Lj ∩Ta

x −xa
) u

≤ 1.
We define
analogously: x00b = 0, x00a = 1. For each vertex v ∈ Ta , we set x00v = 0,
and for each v ∈ Tb , we define x00v = xv /(1 − xb ). It can be checked similarly that (x00 , y00 ) is a
feasible solution.
(1−xa )

(x00 , y00 )

Claim 13. If x is an optimal extreme point, then xa + xb = 1.
Proof. Observe that, for each v ∈ Tb , yv0 = 1 and for each v ∈ Ta , yv0 =
value of x0 is |Tb | +

P

v∈Ta

yv0 = |Tb | +

1
(1−xa )

v∈Ta (yv

P

Similarly, the objective value of solution x00 is |Ta | +
xb
(1−xb ) |Tb |.

9

− xa ) = |Tb | +

1
(1−xb )

v∈Tb (yv

P

yv −xa

P1−xa

. The objective

y
v∈Ta v
(1−xa )

−

− xb ) = |Ta | +

xa
(1−xa )
P
v∈Tb

|Ta |.
yv

(1−xb )

−

Consider the convex combination
has the objective value of

1−xa
0
(2−xa −xb ) x

+

1−xb
00
(2−xa −xb ) x .

This solution is feasible and




1
· (1 − xa − xb ) (|Ta | + |Tb |) +
yv 
(2 − xa − xb )
v∈V (T )
X

If xa + xb < 1, we apply the fact that |Ta | + |Tb | > v∈V (T ) yv to get the objective of strictly
P
more than v∈V (T ) yv , contradicting the fact that (x, y) is optimal.
P

Finally, we define the convex combination by z = (1 − xa )x0 + xa x00 . It can be verified easily
that zv = xv for all v ∈ V (T ).
Finbow et al. Instances: In this instance, the tree has degree at most 3 and the root has
degree 2. Finbow et al. [11] showed that this is polynomial time solvable.
Theorem 14. Let (T, s) be an input instance where T has degree at most 3 and s has degree
two. Let (x, y) be a feasible fractional solution for (LP-3). Then there is a polynomial time
P
algorithm that saves at least v∈V (T ) yv vertices.
Proof. We prove this by induction on the number of nodes in the tree that, for any tree (T 0 , s0 )
that is a Finbow et al. instance, for any fractional solution (x, y) for (LP’), there is an integral
P
P
solution (x0 , y 0 ) such that v∈T 0 \{s0 } yv0 = v∈T 0 \{s0 } yv . Let a and b be the children of the
P
root s. From Lemma 12, assume w.l.o.g. that xa = 1, so we have v∈Ta yv = |Ta |. By
the induction hypothesis, there is an integral solution (x0 , y 0 ) for the subtree Tb such that
P
P
P
0 0
0
0
extended to the instance T
v∈Tb yv . The solution (x , y ) can be P
v∈Tb \{b} yv =
v∈Tb yv =
P
0
by defining xa = 1. This solution has the objective value of |Ta | + v∈Tb yb0 = |Ta | + v∈Tb yb ,
completing the proof.
Bad instance for (LP-1): We show in Figure 1 a Finbow et al.
instance as well as a solution for (LP-1) that is optimal and an extreme
point, but not integral.

a

b

Claim 15. The solution (x, y) represented in Figure 1, with y defined
c
d
according to Proposition 11, is an extreme point of this instance for
(LP-1).
Figure 1 Instance with
Proof. Suppose (for contradiction) that (x, y) is not an extreme point. a non-integral extreme
Then, there are distinct solutions (x0 , y 0 ), (x00 , y 00 ) and α ∈ (0, 1) such point for (LP-1). Gray
vertices: xv = 1/2; oththat (x, y) = α(x0 , y 0 ) + (1 − α)(x00 , y 00 ). Since yc = 1 and yc0 , yc00 ≤ 1, erwise: x =
0.
v
then yc0 = yc00 = 1, and likewise, yd0 = yd00 = 1. Combining that
x0a + x0c = yc0 = 1 with x0a + x0d = yd0 = 1 and x0c + x0d ≤ 1, we conclude
that x0a ≥ 1/2. Similarly, we get that x00a ≥ 1/2, which implies that x0a = x00a = 1/2.
Similar reasoning using that x0a + x0b ≤ 1 allows us to conclude that x0b = x00b = 1/2, and
thus, (x0 , y 0 ) = (x00 , y 00 ) = (x, y), which contradicts our assumption.

4.2

Rounding 1/2-integral Solutions

We say that the LP solution (x, y) is (1/k)-integral if, for all v, we have xv = rv /k for some
integer rv ∈ {0, . . . , k}. By standard LP theory, one can assume that the LP solution is (1/k)integral for some polynomially large integer k.
In this section, we consider the case when k = 2 (1/2-integral LP solutions). From Theorem 5, (LP-1) is not strong enough to obtain a 3/4 +  approximation algorithm, for any  > 0.
Here, we show a 5/6 approximation algorithm based on rounding (LP’).
10

Theorem 16. Given a solution (x, y) for (LP’) that is 1/2-integral, there is a polynomial time
P
algorithm that produces a solution of cost 5/6 v∈V (T ) yv .
We believe that the extreme points in some interesting special cases will be 1/2-integral.
Algorithm’s Description: Initially, U = ∅. Our algorithm considers the layers L1 , . . . , Ln
in this order. When the algorithm looks at layer Lj , it picks a vertex uj and adds it to U, as
follows. Consider Aj ⊆ Lj , where Aj = {v ∈ Lj : xv > 0}. Let A0j ⊆ Aj contain vertices v such
that there is no ancestor of v that belongs to Aj 0 for some j 0 < j, and A00j = Aj \ A0j , i.e. for
each v ∈ A00j , there is another vertex u ∈ Aj 0 for some j 0 < j such that u is an ancestor of v.
We choose the vertex uj based on the following rules:
• If there is only one v ∈ Aj , such that v is not saved by U so far, choose uj = v.
• Otherwise, if |A0j | = 2, pick uj at random from A0j with uniform probability. Similarly, if
|A00j | = 2, pick uj at random from A00j .
• Otherwise, we have the case |A0j | = |A00j | = 1. In this case, we pick vertex uj from A0j with
probability 1/3; otherwise, we take from A00j .
Analysis: Below, we argue that each vertex v ∈ V (T ) : xv > 0 is saved with probability
at least (5/6)yv . It is clear that this implies the theorem: Consider a vertex v 0 : xv0 = 0. If
yv0 = 0, we are immediately done. Otherwise, consider the bottommost ancestor v of v 0 such
that xv > 0. Since yv = yv0 , the probability that v 0 is saved is the same as that of v, which is
at least (5/6)yv .
We analyze a number of cases. Consider a layer Lj such that |Aj | = 1. Such a vertex v ∈ Aj
is saved with probability 1.
Next, consider a layer Lj such that |A0j | = 2. Each vertex v ∈ A0j is saved with probability
1/2 and yv = 1/2. So, in this case, the probability of saving v is more than (5/6)yv .
Lemma 17. Let Lj be the layer such that |A0j | = |A00j | = 1. Then the vertex u ∈ A0j is saved
with probability 2/3 ≥ (5/6)yu and vertex v ∈ A00j is saved with probability 5/6.
Proof. Let v 0 ∈ Aj 0 be the ancestor of v in some layer above Aj . The fact that v has not been
saved means that v 0 is not picked by the algorithm, when it processed Aj 0 .
We prove the lemma by induction on the value of j. For the base case, let Lj be the first
layer such that |A0j | = |A00j | = 1. This means that the layer Lj 0 must have |A0j 0 | = 2, and
therefore the probability of v 0 being saved is at least 1/2. Vertex u is not saved only if both
v 0 and u are not picked, and this happens with probability 1/2 · 2/3 = 1/3. Hence, vertex u is
saved with probability 2/3 as desired. Consider now the base case for vertex v, which is not
saved only if v 0 is not saved and u is picked by the algorithm among {u, v}. This happens with
probability 1/2 · 1/3 = 1/6, thus completing the proof of the base case.
For the purpose of induction, we now assume that, for all layer Li above Lj such that
|A0i | = |A00i | = 1, the probability that the algorithm saves the vertex in A0i is at least 2/3. Since
the vertex u is not saved only if v 0 is not saved, this probability is either 1/2 or 1/3 depending
on the layer to which v 0 belongs. If it is 1/3, we are done; otherwise, the probability is at most
1/2 · 2/3 = 1/3. Now consider vertex v, which is not saved only if v 0 is not saved and u is picked
at Lj . This happens with probability at most 1/2 · 1/3 = 1/6.
Lemma 18. Let Lj be a layer such that A00j = {u, v} (containing two vertices). Then each such
vertex is saved with probability at least 5/6.

11

Proof. Let u0 and v 0 be the ancestors of u and v in some sets A0i and A0k above the layer Lj .
There are the two possibilities: either both u0 and v 0 are in layers with |A0i | = |A0k | = 2 (maybe
i = k); or u0 is in the layer with |A0i | = |A00i | = 1. We remark that u0 6= v 0 : otherwise, the LP
constraint for v 0 and Lj would not be satisfied.
For u or v to be unsaved, we need that both u0 and v 0 are not saved by the algorithm.
Otherwise, if, say, u0 is saved, u is also saved, and the algorithm would have picked v.
P [u is not saved] = P [u not picked ∧ u0 is not saved ∧ v 0 is not saved]
= P [u not picked] · P [u0 is not saved ∧ v 0 is not saved]
1
1 1
= · =
2 4
8
7
5
P [u is saved] = ≥
8
6
It must be that P [u0 burns ∧ v 0 burns] ≤ 1/4, since either u0 and v 0 are in different layers or
they are in the same layer. If they are in different layers, picking each of them is independent,
and the probability of neither being saved is at most 1/4. If they are in the same layer, one
of them is necessarily picked, which implies that the probability of neither being saved is 0. In
any case, the probability is at most 1/4.
In the second case, at least one of the vertices u0 , v 0 is in a layer with one 2-special vertex.
W. l. o. g. let u0 be in such a layer. By Lemma 17, we know that the probability that u0 is not
saved is at most 1/3. Therefore,
P [u burns] = P [u not picked ∧ u0 burns ∧ v 0 burns]
= P [u not picked] · P [u0 burns ∧ v 0 burns]
≤ P [u not picked] · P [u0 burns]
1 1
1
≤ · =
2 3
6
5
P [u is saved] ≥
6
The proof for both cases works analogously for v.

4.3

Ruling Out the Gap Instances in Section 3

In this section, we show that the integrality gap instances for (LP-1) presented in the previous
section admit a better than (1 − 1/e) approximation via (LP’). To this end, we introduce the
concept of well-separable LP solutions and show an improved rounding algorithm for solutions
in this class.
Let η ∈ (0, 1). Given an LP solution (x, y) for (LP-1) or (LP’), we say that a vertex v is
P
η-light if u∈Pv \{v} xu < η; if a vertex v is not η-light, we say that it is η-heavy. A fractional
solution is said to be η-separable if for all layer j, either all vertices in Lj are η-light, or they
are all η-heavy. For an η-separable LP solution (x, y), each layer Lj is either an η-light layer
that contains only η-light vertices, or η-heavy layer that contains only η-heavy vertices.
Observation 19. The LP solution in Section 3 is η-separable for all values of η ∈ {1/k, 2/k, . . . , 1}.
Theorem 20. If the LP solution (x, y) is η-separable for some η, then there is an efficient
P
algorithm that produces an integral solution of cost (1 − 1/e + f (η)) v yv , where f (η) is some
function depending only on η.
12

Algorithm: Let T be an input tree, and (x, y) be a solution for (LP’) on T that is ηseparable for some constant η ∈ (0, 1). Our algorithm proceeds in two phases. In the first
phase, it performs randomized rounding independently for each η-light layer. Denote by V1 the
(random) collection of vertices selected in this phase. Then, in the second phase, our algorithm
performs randomized rounding conditioned on the solutions in the first phase. In particular,
when we process each η-heavy layer Lj , let L̃j be the collection of vertices
that

 have not yet been

saved by V1 . We sample one vertex v ∈ L̃j from the distribution

xv
x(L̃j )

. Let V2 be the

v∈L̃j

set of vertices chosen from the second phase. This completes the description of our algorithm.
For notational simplification, we present the proof when η = 1/2. It will be relatively
obvious that the proof can be generalized to work for any η. Now we argue that each terminal
t ∈ X is saved with probability at least (1 − 1/e + δ)yt for some universal constant δ > 0
that depends only on η. We will need the following simple observation that follows directly by
standard probabilistic analysis.
Proposition 21. For each vertex v ∈ V (T ), the probability that v is not saved is at most
Q
−yv .
u∈Pv (1 − xu ) ≥ 1 − e
We start by analyzing two easy cases.
Lemma 22. Consider t ∈ X . If yt < 0.9 or there is some ancestor v ∈ Pt such that xv > 0.2,
then the probability that v is saved by the algorithm is at least (1 − 1/e + δ)yt .
Proof. First, let us consider the case where yt < 0.9. The probability of t being saved is at
least 1 − e−yv , according to the straightforward analysis. If yt < 0.9, we have 1 − e−yt /yt >
1.04(1 − 1/e)yt as desired.
Consider now the second case when xv > 0.2 for some ancestor v ∈ Pt . The bound used
typically in the analysis is only tight when the values are all small, and, therefore, we get an
advantage when one of the values is relatively big. In particular,
Pr [t is saved] ≥ 1 −

Y

(1 − xu )

u∈Pt

≥ 1 − (1 − xv )e−(yt −xv )
≥ 1 − (1 − 0.2)e−(yt −0.2)
≥ 1.01(1 − 1/e)yv

From now on, we only consider those terminals t ∈ X such that yt ≥ 0.9 and xv < 0.2, for
all v ∈ Pt . We remark here that if the value of η is not 1/2, we can easily pick other suitable
thresholds instead of 0.9 and 0.2.
For each vertex v ∈ V , let X1 ⊆ X be the set of terminals that are saved by V1 , i.e. a vertex
t ∈ X1 if and only if t is a descendant of some vertex in V1 . Let X2 ⊆ X \ X1 contain the set of
terminals that are not saved by the first phase, but are saved by the second phase, i.e. t ∈ X2
if and only if t has some ancestor in V2 .
PrV1 ,V2 [t 6∈ X1 ∪ X2 ] = PrV1 ,V2 [t 6∈ X1 ] PrV1 ,V2 [t 6∈ X2 : t 6∈ X1 ]
For any terminal t, let St0 and St00 be the sets of ancestors of t that are η-light and η-heavy
respectively, i.e. ancestors in St0 and St00 are considered by the algorithm in Phase 1 and 2
0
respectively. By Proposition 21, we can upper bound the first term by e−x(St ) . In the rest of
13

00

this section, we show that the second term is upper bounded by e−x(St ) c for some c < 1, and
0
00
therefore Pr [t 6∈ X1 ∪ X2 ] ≤ ce−x(St )−x(St ) ≤ ce−yt , as desired.
The following lemma is the main technical tool we need in the analysis. We remark that
this lemma is the main difference between (LP’) and (LP-2).
Lemma 23. Let t ∈ X and Lj be a layer containing some η-heavy ancestor of t. Then
EV1 [x(L̃j ) | t 6∈ X1 ] ≤ α
1
+ (1 − e−1/2 ) ≤ 0.9
2
Intuitively, this lemma says that any terminal that is still not saved by the result of the first
phase will have a relatively “sparse” layer above it. We defer the proof of this lemma to the
next subsection. Now we proceed to complete the analysis.
For each vertex v, denote by `(v) the layer to which vertex v belongs. For a fixed choice of
P
V1 , we say that terminal t is partially protected by V1 if v∈St00 xv x(L̃`(v) ) ≤ Cx(St00 ) (we will
choose the value of C ∈ (α, 1) later). Let X 0 ⊆ X \ X1 denote the subset of terminals that are
partially protected by V1 .
for α =

Claim 24. For any t ∈ X , PrV1 [t ∈ X 0 | t 6∈ X1 ] ≥ 1 − α/C.
Proof. By linearity of expectation and Lemma 23,


EV1 


X

xv x(L̃`(v) ) | t 6∈ X1  =

v∈St00

X

h

i

xv EV1 x(L̃`(v) ) | t 6∈ X1 ≤ αx(St00 )

v∈St00

Using Markov’s inequality,




PrV1 

X

xv x(L̃`(v) ) ≤ Cx(St00 ) | t 6∈ X1 

v∈St00



= 1 − Pr 
≥1−
=1−


X

xv x(L̃`(v) ) > Cx(St00 ) | t 6∈ X1 

v∈St00
αx(St00 )
Cx(St00 )

α
C

We can now rewrite the probability of a terminal t ∈ X not being saved by the solution
after the second phase.
PrV1 ,V2 [t 6∈ X2 | t 6∈ X1 ]
= Pr t ∈ X 0 | t 6∈ X1 Pr t 6∈ X2 | t ∈ X 0 + Pr t 6∈ X 0 | t 6∈ X1 Pr t 6∈ X2 | t 6∈ X 0


α
00
≤ (1 − α/C)PrV1 ,V2 t 6∈ X2 | t ∈ X 0 + · e−x(St )
C














00



The last inequality holds because PrV1 ,V2 [t 6∈ X2 | t 6∈ X 0 ] is at most e−x(St ) from Proposition 21.
It remains to provide a better upper bound for Pr [t 6∈ X2 | t ∈ X 0 ]. Consider a vertex
v ∈ St00 that is involved in the second phase rounding. We say that vertex v is good for t and
14

V1 if x(L̃`(v) ) ≤ C 0 (we will choose the value C 0 ∈ (C, 1) later.) Denote by Stgood ⊆ St00 the set
of good ancestors of t. The following claim ensures that good ancestors have large LP-weight
in total.
Claim 25. For any node t ∈ X 0 , x(Stgood ) =

P

xv ≥ (1 − C/C 0 )x(St00 ).

v∈Stgood

Proof. Suppose (for contradiction) that the fraction of good layers was less than 1 − C/C 0 . This
means that x(St00 \ Stgood ) ≥ C/C 0 . For each such v ∈ St00 \ Stgood , we have x(L̃(v)) > C 0 . Then,
P
P
x C 0 ≥ C. This contradicts the assumption that t is partially
v∈St00 xv x(L̃`(v) ) >
v∈St00 \Stgood v
protected, and concludes our proof.
Now the following lemma follows.
Lemma 26. PrV1 ,V2 [t 6∈ X2 | t ∈ X 0 ] ≤ e−x(St ) e−(1− C 0 )x(St )( C 0 −1)
C

00

00

1

Proof.
PrV1 ,V2 t 6∈ X2 | t ∈ X 0


=



PrV1 V1 = V10 PrV2 t 6∈ X2 | V1 = V10

X









V10 :t∈X 0

≤

PrV1 V1 = V10

X





V10 :t∈X 0

≤



V10 :t∈X 0

≤

X

bad v∈St00

PrV1

1−

good v∈St00

e−xv

Y



Y

bad v∈St00
0

PrV1 V1 = V1

X

(1 − xv )

Y

Y

e−xv /C

xv
C0



0

good v∈St00


0
00
0
00 C
V1 = V10 e−x(St ) C 0 −(1−C/C )x(St )/C



V10 :t∈X 0
00

C

0

00

≤ e−x(St ) C 0 −(1−C/C )x(St )/C

0

X

PrV1 V1 = V10




V10 :t∈X 0
00

C

0

00

0

≤ e−x(St ) C 0 −(1−C/C )x(St )/C
1
0
00
00
≤ e−x(St ) e−(1−C/C )x(St )( C 0 −1)

Now we choose the parameters C and C 0 such that C = (1 + δ)α, C 0 = (1 + δ)C, and
(1 + δ)C 0 = 1, where (1 + δ)3 = 1/α. Notice that this choice of parameters satisfy our previous requirements that α < C < C 0 < 1. The above lemma then gives the upper bound of
00

δ2

00

00

e−x(St ) e− 1+δ x(St ) , which is at most e−(1+δ /2)x(St ) . Since δ > 0 is a constant, notice that we
do have an advantage over the standard LP rounding in this case. Now we plug in all the
parameters to obtain the final result.
2

PrV1 ,V2 [t 6∈ X1 ∪ X2 ] = PrV1 ,V2 [t 6∈ X1 ] PrV1 ,V2 [t 6∈ X2 | t 6∈ X1 ]
0



(1 − α/C) PrV1 ,V2 t 6∈ X2 | t ∈ X 0 +

0



(1 − α/C) e−x(St ) e− 2 x(St ) +

≤ e−x(St )
≤ e−x(St )
≤ e−yt



≤ e−yt





00

δ2

00



δ2

(1 − α/C) e− 2 x(St ) + α/C

00



δ −(1+δ2 /2)x(St00 )
1
e
+
1+δ
1+δ
15



α −x(St00 )
e
C

α −x(St00 )
e
C





Since we assume that yt > 0.9 and xv ≤ 0.2, we must have x(St00 ) ≥ 0.2, and therefore the
above term can be seen as e−yt · δ 0 for some δ 0 < 1. Overall, the approximation factor we get is
(1 − δ 0 /e) for some universal constant δ 0 ∈ (0, 1).
4.3.1

Proof of Lemma 23

For each u, let Eu denote the event that u is not saved by V1 . First we break the expectation
P
term into u∈Lj xu Pr [Eu | t 6∈ X1 ]. Let v ∈ L be the ancestor of t in layer Lj . We break down
the sum further based on the “LP coverage” of the least common ancestor between u and v, as
follows:
k/2
X

xu Pr [Eu | t 6∈ X1 ]

X

i=0 u∈Lj :q 0 (lca(u,v))=i

Here, q 0 (u) denotes k · x(Pu ); this term is integral since we consider the 1/k-integral solution
(x, y). The rest of this section is devoted to upper bounding the term Pr [Eu | t 6∈ X1 ]. The
following claim gives the bound based on the level i to which the least common ancestor belongs.
Claim 27. For each u ∈ Lj such that q 0 (lca(u, v)) = i,
Pr [Eu | t 6∈ X1 ] ≤ e−(1/2−i/k)
Proof. First, we recall that yu ≥ 1/2 and q 0 (u) ≥ k/2, since u is in the 1/2-heavy layer Lj . Let
w = lca(u, v) and P 0 be the path that connects w to u. Moreover, denote by S ⊆ P 0 the set of
P
P
light vertices on the path P 0 , i.e. S = St0 ∩ P 0 . Notice that x(S) ≥ a∈St0 ∩Pu xa − a∈Pw xa ≥
(1/2 − i/k).
For each w0 ∈ S, Pr [w0 6∈ V1 | t 6∈ X1 ] ∈ {1 − xw0 , 1 − xw0 /(1 − xv0 )} depending on whether
there is a vertex v 0 in Pv that shares a layer with w0 . In any case, it holds that Pr [w0 6∈ V1 | t 6∈ X1 ] ≤
(1 − xw0 ). This implies that
Pr [Eu | t 6∈ X1 ] ≤

Y

Pr w0 6∈ V1 | t 6∈ X1




w0 ∈S

≤

Y

(1 − xw0 )

w0 ∈S

≤

Y

e−xw0

w0 ∈S
−(1/2−i/k)

≤e

Claim 28. Let i be an integer and L0 ⊆ Lj be the set of vertices u such that q 0 (lca(u, v)) is at
least i. Then x(L0 ) ≤ (k − i)/k.
Proof. This claim is a consequence of Hartke’s constraints. Let v 0 be the topmost ancestor of v
such that q 0 (v 0 ) ≥ i. We remark that all vertices in L0 must be descendants of v 0 , so it must be
P
that w∈Pv0 xw + x(L0 ) ≤ 1. The first term is i/k, implying that x(L0 ) ≤ (k − i)/k.
Let Lij ⊆ Lj denote the set of vertices u whose least common ancestor lca(u, v) satisfies
P
0
q 0 (lca(u, v)) = i. As a consequence of Claim 28, i0 ≥i x(Lij ) ≤ (k − i)/k. Combining this
inequality with Claim 27, we get that
h

i

E x(L̃j ) | t 6∈ X1 ≤

k/2
X

x(Lij )e−1/2+i/k

i=0

16

k/2

This term is maximized when x(Lj ) = 1/2 and x(Lij ) = 1/k for all other i = 0, 1, . . . , k/2−
1. This implies that
k/2−1

h

i

E x(L̃j ) | t 6∈ X1 ≤ 1/2 +

X

e−1/2+i/k /k

i=0

Finally, using some algebraic manipulation and the fact that 1 + x ≤ ex , we get
k/2−1

h

i

E x(L̃j ) | t 6∈ X1 ≤ 1/2 +

X

e−1/2+i/k /k

i=0

1 −1/k 1 − e−1/2
e
k
1 − e−1/k
1/k
1
= 1/2 + (1 − e−1/2 ) 1/k
e
1 − e−1/k
1/k
= 1/2 + (1 − e−1/2 ) 1/k
e −1
≤ 1/2 + (1 − e−1/2 )
= 1/2 +

4.4

Integrality Gap for (LP’)

In this section, we present an instance where (LP’) has an integrality gap of 5/6 + , for any
 > 0. Interestingly, this instance admits an optimal 21 -integral LP solution.
Gadget: The motivation of our construction is a simple gadget represented in Figure 2.
In this instance, vertices are either special (colored gray) or regular. This gadget has three
properties of our interest:
• If we assign an LP-value of xv = 1/2 to every special vertex, then this is a feasible LP
solution that ensures yu = 1 for all leaf u.
• For any integral solution U that does not pick any vertex in the first layer of this gadget,
at most 2 out of 3 leaves of the gadget are saved.
• Any pair of special vertices in the same layer do not have a common ancestor inside this
gadget.
Our integrality gap instance is constructed by creating partially
overlapping copies of this gadget. We describe it formally below.
Construction: The first layer of this instance, L1 , contains 4 nodes:
two special nodes, which we name a(1) and a(2), and two regular
nodes, which we name b(1) and b(2). We recall the definition of spider
from Section 3.1.
Let α = 5 d1/e. The nodes b(1) and b(2) are the roots of two Figure 2 Gadget used
spiders. Specifically, the spider Z1 rooted at b(1) has α feet, with one to get 5/6 integrality
foot per layer, in consecutive layers L2 , . . . , Lα+1 . For each j ∈ [α], gap. Special vertices are
denote by b0 (1, j), the j th foot of spider Z1 . The spider Z2 , rooted at colored gray.
b(2), has α2 feet, with one foot per layer, in layers Lα+2 , . . . , Lα2 +α+1 .
For each j ∈ [α2 ], denote by b0 (2, j), the j th foot of spider Z2 . All the
feet of spiders Z1 and Z2 are special vertices.
0 , with α2 feet, lying in the α2
For each j ∈ [α], the node b0 (1, j) is also the root of spider Z1,j
consecutive layers L2+α+jα2 , . . . , L1+α+(j+1)α2 (one foot per layer). For j 0 ∈ [α2 ], let b00 (1, j, j 0 )
17

0 that lies in layer L
3
denote the j 0 -th foot of spider Z1,j
1+α+jα2 +j 0 . Notice that we have α such

feet of these spiders
[α2 ],

n

0
Z1,j

b0 (2, j)

oα

j=1

lying in layers L2+α+α2 , . . . , L1+α+α2 +α3 . Similarly, for each

0
j ∈
the node
is the root of spider Z2,j
with α2 feet, lying in consecutive layers
L2+α+α3 +jα2 , . . . , L1+α+α3 +(j+1)α2 . We denote by b00 (2, j, j 0 ) the j 0 -th foot of this spider.
The special node a(1) is also the root of spider W1 which has α + α3 feet: The first α feet,
denoted by a0 (1, j) for j ∈ [α], are aligned with the nodes b0 (1, j), i.e. for each j ∈ [α], the foot
a0 (1, j) of spider W1 is in the same layer as the foot b0 (1, j) of Z1 . For each j ∈ [α], j 0 ∈ [α2 ], we
also have a foot a00 (1, j, j 0 ) which is placed in the same layer as b00 (1, j, j 0 ). Similarly, the special
node a(2) is the root of spider W2 having α2 + α4 feet. For j ∈ [α2 ], spider W2 has a foot a0 (2, j)
placed in the same layer as b0 (2, j). For j ∈ [α2 ], j 0 ∈ [α2 ], W2 also has a foot a00 (2, j, j 0 ) in the
layer of b00 (2, j, j 0 ). All the feet of both W1 and W2 are special vertices.
Finally, for i ∈ {1, 2}, and j ∈ [αi ], each node a0 (i, j) has α5−i children, which are leaves
of the instance. For j ∈ [α], j 0 ∈ [α2 ], the nodes b00 (i, j, j 0 ), a00 (i, j, j 0 ) have α3−i children each
which are also leaves of the instance. The set of terminals X is simply the set of leaves.

Proposition 29. We have |X | = 6α5 . Moreover, (i) the number of terminals in subtrees
Ta(1) ∪ Tb(1) is 3α5 , and (ii) the number of terminals in subtrees Ta(2) ∪ Tb(2) is 3α5 .
Proof. Each node a0 (1, j) has α4 children, and there are α such nodes. Similarly, each node
a0 (2, j) has α3 children. There are α2 such nodes. This accounts for 2α5 terminals.
For i ∈ {1, 2}, each node a00 (i, j, j 0 ) has α3−i children. There are αi+2 such nodes. This
accounts for another 2α5 terminals. Finally, there are α3−i children of each b00 (i, j, j 0 ), and
there are α2+i such nodes.

Fractional Solution: Our construction guarantees that any path from root to leaf contains 2
special vertices: For a leaf child of a0 (i, j), its path towards the root must contain a0 (i, j) and
a(i). For a leaf child of a00 (i, j, j 0 ), its path towards the root contains a00 (i, j, j 0 ) and a(i). For a
leaf child of b00 (i, j, j 0 ), the path towards the root contains b00 (i, j, j 0 ) and b0 (i, j).
Lemma 30. For each special vertex v, for each layer Lj below v, the set Lj ∩ Tv contains at
most one special vertex.
Proof. Each layer contains two special vertices of the form {a0 (i, j), b0 (i0 , j 0 )} or {a00 (i, j), b00 (i0 , j 0 )}.
In any case, the least common ancestor of such two special vertices in the same layer is always
the root s (since one vertex is in Ta(i) , while the other is in Tb(i) ) This implies that, for any
non-root vertex v, the set Lj ∩ Tv can contain at most one special vertex.
Notice that, there are at most two special vertices per layer. We define the LP solution x,
with xv = 1/2 for all special vertices v and xv = 0 for all other vertices. It is easy to verify that
this is a feasible solution.
P
We now check the constraint at v and layer Lj below v: If the sum u∈Pv xu = 0, then the
P
P
constraint is immediately satisfied, because u∈Lj ∩Tv xu ≤ 1. If u∈Pv xu = 1/2, let v 0 be the
P
P
special vertex ancestor of v. Lemma 30 guarantees that u∈Lj ∩Tv xu ≤ u∈Lj ∩Tv0 xu ≤ 1/2,
P
and therefore the constraint at v and Lj is satisfied. Finally, if u∈Pv xu = 1, there can be no
P
special vertex below v and therefore u∈Lj ∩Tv xu = 0.
Integral Solution: We argue that any integral solution cannot save more than (1 + 5/α)5α5
terminals. The following lemma is the key to our analysis.
Lemma 31. Any integral solution U : U ∩{a(1), b(1)} = ∅ saves at most (1+5/α)5α5 terminals.

18

Proof. Consider the set Q = {a0 (1, j)}αj=1 ∪{b0 (1, j)}αj=1 , and a collection of paths from {a(1), b(1)}
to vertices in set Q. These paths are contained in the layers L1 , . . . , Lα+1 , so the strategy U
induces a cut of size at most α + 1 on them. This implies that at most α + 1 vertices (out of
2α vertices in Q) can be saved by U. Let Q̃ ⊆ Q denote the set of vertices that have not been
saved by U. We remark that |Q̃| ≥ α − 1. We write Q̃ = Q̃a ∪ Q̃b where Q̃a contains the set of
vertices a0 (1, j) that are not saved, and Q̃b = Q̃ \ Q̃a . For each vertex in Q̃a , at least α4 − 1 of
its children cannot be saved, so we have at least (α4 − 1)|Q̃a | ≥ α4 |Q̃a | − α unsaved terminals
that are descendants of Q̃a . If |Q̃b | ≤ 3, we are immediately done: We have |Q̃a | ≥ α − 4, so
(α4 − 1)(α − 4) ≥ α5 − 5α4 unsaved terminals.
Consider the set


R=

[

 
 00
a (1, j, j 0 )  ∪ 

j∈[α],j 0 ∈[α2 ]

[


[ 
b00 (1, j, j 0 ) 

j:b0 (1,j)∈Q̃b j 0 ∈[α2 ]

This set satisfies |R| = α3 + |Q̃b |α2 , and the paths connecting vertices in R to Q̃b ∪ {a(1)} lie
in layers L1 , . . . , Lα3 +α2 +α+1 . So the strategy U induced on these paths disconnects at most
α3 + α2 + α + 1 vertices. Let R̃ ⊆ R contain the vertices in R that are not saved by U, so we
have |R̃| ≥ (|Q̃b | − 1)α2 − α − 1, which is at least (|Q̃b | − 2)α2 . Each vertex in R̃ has α2 children.
We will have (α2 − 1) unsaved terminals for each such vertex, resulting in a total of at least
(α2 − 1)(|Q̃b | − 2)α2 ≥ α4 |Q̃b | − 4α4 terminals that are descendants of b(1).
In total, by summing the two cases, at least (α4 |Q̃a |−α)+(α4 |Q̃b |−4α4 ) ≥ (|Q̃a |+|Q̃b |)α4 −
4
5α ≥ α5 − 5α4 terminals are not saved by U, thus concluding the proof.
Lemma 32. Any integral solution U : U ∩{a(2), b(2)} = ∅ saves at most (1+5/α)5α5 terminals.
Since nodes a(1), a(2), b(1), b(2) are in the first layer, it is only possible to save one of them.
Therefore, either Lemma 31 or Lemma 32 apply, which concludes the analysis.

5

Conclusion and Open Problems

In this paper, we settled the integrality gap question for the standard LP relaxation. Our results
ruled out the hope to use the canonical LP to obtain better approximation results. While a
recent paper settled the approximability status of the problem [1], the question whether an
improvement over (1−1/e) can be done via LP relaxation is of independent interest. We provide
some evidences that Hartke’s LP is a promising candidate for doing so. Another interesting
question is to find a more general graph class that admits a constant approximation algorithm.
We believe that this is possible for bounded treewidth graphs.

References
[1] Adjiashvili, D., Baggio, A., Zenklusen, R.: Firefighting on Trees Beyond Integrality Gaps.
ArXiv e-prints (Jan 2016)
[2] Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the firefighter
problem - computing cuts over time. Algorithmica 62(1-2), 520–536 (2012)
[3] Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen, E.J.:
Parameterized complexity of firefighting. JCSS 80(7) (2014)

19

[4] Bazgan, C., Chopin, M., Ries, B.: The firefighter problem with more than one firefighter
on trees. Discrete Applied Mathematics 161(7-8), 899–908 (2013)
[5] Cai, L., Verbin, E., Yang, L.: Firefighting on trees: (1-1/e)-approximation, fixed parameter
tractability and a subexponential algorithm. In: ISAAC (2008)
[6] Chalermsook, P., Chuzhoy, J.: Resource minimization for fire containment. In: SODA
(2010)
[7] Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and
applications. In: APPROX 2004. pp. 72–83 (2004)
[8] Chlebíková, J., Chopin, M.: The firefighter problem: A structural analysis. In: Cygan, M.,
Heggernes, P. (eds.) IPEC. Lecture Notes in Computer Science, vol. 8894, pp. 172–183.
Springer (2014)
[9] Costa, V., Dantas, S., Dourado, M.C., Penso, L., Rautenbach, D.: More fires and more
fighters. Discrete Applied Mathematics 161(16–17), 2410 – 2419 (2013)
[10] Develin, M., Hartke, S.G.: Fire containment in grids of dimension three and higher. Discrete
Applied Mathematics 155(17), 2257–2268 (2007)
[11] Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and
questions. Australas. J. Combin 43, 57–77 (2009)
[12] Hartke, S.G.: Attempting to narrow the integrality gap for the firefighter problem on trees.
Discrete Methods in Epidemiology 70, 179–185 (2006)
[13] Hartnell, B.: Firefighter! an application of domination. In: Manitoba Conference on Combinatorial Mathematics and Computing (1995)
[14] Iwaikawa, Y., Kamiyama, N., Matsui, T.: Improved approximation algorithms for firefighter problem on trees. IEICE Transactions 94-D(2), 196–199 (2011)
[15] King, A., MacGillivray, G.: The firefighter problem for cubic graphs. Discrete Mathematics
310(3), 614–621 (2010)
[16] Wang, P., Moeller, S.A.: Fire control on graphs. Journal of Combinatorial Mathematics
and Combinatorial Computing 41, 19–34 (2002)

20

A

Omitted Figures

21

k

kD

D2

D

D

. . . . . . . . . . . . . . . .
Figure 3 Simplified example of the instance used to achieve integrality gap of 1 − 1/e, when k = 2 and
D = 2. The labels in the figure indicate, in general, the number of edges in that location, in terms of k
and D. Special vertices are colored gray.

y1

y2

x2

x1

... ...
...
...
...
...
...
...
Figure 4 Simplified example of the instance with low integrality gap for 1/2-integral solutions. Special
vertices are colored gray.

22

