Search Results

The firefighting game is a fundamental problem in theoretical computer science, modeling the containment of a spreading process under limited defensive resources. In each round, an algorithm may protect a set of vertices by placing firefighters on them, preventing the fire from spreading to those vertices. Vertices that are never reached by the fire are said to be saved. The goal is to maximize the number of saved vertices. While the offline version has been extensively studied, much less is known about the competitive complexity of the online variant, where the underlying graph is known in advance but the number of available firefighters in each round is revealed online. We study how graph structure governs the power of the adversary in the online firefighting game. On trees, the problem is known to be 2-competitive (Coupechoux et al., 2019), a result that relies on a strong structural alignment between the online algorithm and the offline optimal solution throughout the process. We show that this alignment breaks down as soon as cycles are present. In particular, the algorithm and the offline optimal solution may break a cycle differently, or even break different cycles, and therefore operate on fundamentally different residual graphs. As a result, the adversary gains additional leverage by steering the process along residual graph structures that no longer admit a direct comparison between the algorithm and the offline optimal solution. Our main result shows that the presence of a single cycle already increases the competitive complexity of the firefighting game dramatically. We first show that even on a tadpole graph (a cycle with a tail), no deterministic online algorithm can achieve a competitive ratio better than Ω(√n), where n is the number of vertices. We complement this lower bound with matching upper bounds by designing an O(√n)-competitive online algorithm for 1-almost trees, that is, graphs obtained from a tree by adding at most one edge. Furthermore, we extend our framework to cactus graphs and prove that, despite the presence of multiple cycles, the competitive complexity remains Θ(√n) as long as the cycles do not share edges. Together, these results yield a tight characterization of the adversarial power induced by cycles with non-overlapping edges. Finally, considering that cactus graphs have treewidth of 2, we study a variant in which firefighters are released in pairs, that is, an even number of firefighters becomes available in each round. Surprisingly, the competitive complexity is significantly reduced to 3-competitive for this setting.