Session 1C — Lectures by Fellows/Associates

Renee M. Borges, IISc, Bengaluru

Algorithmic Aspects of the Firefighting Problem View Presentation

This talk will present some results about specific types of games on graphs, which are a powerful tool to model various real-world applications. Our focus will be mostly on the algorithmic aspects of the firefighter game, which is a turn-based game played on a graph, where the fire spreads to vertices in a breadth-first manner from a source, and firefighters can be placed on yet unburnt vertices on alternate rounds to block the fire. The Firefighter problem was introduced in 1995 and intended to capture also important applications, like understanding the spread of news on a social network, or developing a strategy for immunizing a population against a virus. The goal here is to come up with a strategy for placing firefighters on nodes in order to intercept the spread of the fire. The most 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, minimizing the number of rounds, the number of firefighters per round, or the number of burned vertices, 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 talk, we will survey some of the known results and techniques for solving the firefighting problem, with a special focus on the variant where the goal is to save a critical subset of nodes. In this context, we will draw connections with notions of important separators and tight separator sequences. We will also contemplate on possible relationships that this problem has with other models of information spread on networks.