The
firefighter problem is defined as follows. Initially,
a fire breaks out at a vertex of a graph. In each subsequent
time unit, a firefighter chooses a vertex not yet on fire
and protects it, and the fire spreads to all unprotected
neighbors of the vertices on fire. The objective is to
choose a sequence of vertices for the firefighter to protect
so as to save the maximum number of vertices. The firefighter
problem can be used to model the spread of fire, diseases,
computer viruses and suchlike in a macro-control level.
In
this talk, we consider algorithmic aspects of the firefighter
problem on trees, which is NP-hard even for trees of maximum
degree 3. We focus on the fixed-parameter tractability
(FPT) of the problem and present FPT algorithms based
on kernelization and a novel random separation method
of Cai, Chan and Chan. We will also give a (1-1/e)-approximation
algorithm based on LP-rounding.