Online Firefighting on Cactus Graphs

Abstract

The FIREFIGHTER problem is a turn-based game on a graph in which a spreading fire must be contained by protecting vertices. We study the online variant, where each decision is made without knowledge of future events. While previous research has established an optimal 2-competitive algorithm for trees, we extend the analysis to cactus graphs. For this class, we present an O(√n)-competitive algorithm and prove, via a matching lower bound, that it is optimal. We then analyze a variant where an even number of firefighters is released each round (a multiple of the treewidth 2). We show that under this restriction the competitive ratio drops from O(√n) to a constant: a greedy algorithm is exactly 3-competitive.