Atlantic Graph Theory Seminar: Mohammad Salavatipour, U. Alberta

Approximation Schemes for Resource Minimization for Fire Containment

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of
harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected
tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters
can protect up to B vertices of the graph while the fire spreads from burning vertices to all their
neighbors that have not been protected so far. The task is to find the smallest B that allows for
saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2
even on trees unless P = NP.

In this talk we present an asymptotic QPTAS for RMFC on trees. More specifically, let \eps > 0,
and F be an instance of RMFC where the optimum number of firefighters to save all the leaves is
OPT(F). We present an algorithm which uses at most \ceil(1 + \eps )OPT(F)\rceil many firefighters at each
time step and runs in time n^O(\log\log n). This suggests that the existence of an asymptotic PTAS is
plausible especially since the exponent is O(log log n).

————————————————————-
Join Zoom Meeting
https://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09

Meeting ID: 864 1523 0827
Passcode: 835547