Online Firefighting on Cactus Graphs

Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu · 2025

Read Online Firefighting on Cactus Graphs by Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22277.txt.

Introduction

Max Hugen, Bob Krekelberg, and Alison Hsiang-Hsuan Liu study firefighting on graphs, a game where fire spreads along edges and firefighters protect one vertex per round, choosing without knowing the future. On trees, a simple strategy is known to be nearly optimal. Their 2025 paper asks what changes when the graph has cycles. Cycles, they show, hand the adversary real power: the algorithm and the ideal solution may cut different cycles, leaving them playing on different boards.

Even on a tadpole graph, one cycle with a tail, they prove no deterministic online strategy can guarantee a good competitive ratio. They then give a matching strategy for graphs with at most one cycle, and extend it to cactus graphs, where many cycles appear but barely touch. A variant where firefighters arrive in pairs changes the picture completely: the problem becomes constant-competitive.

Catalog record

CREATORMax Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-22277

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Firefighting on Cactus Graphs Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu Abstract The firefighting game is an important problem in theoretical computer science. It has been broadly studied in the offline model, including results on computational complexity for various graph classes. In this work, we investigate the online setting and the competitive complexity , which has been relatively less explored. In the online setting, the graph is given in advance, but the sequence of available firefighters is revealed in an online manner. The online algorithm aims to save as many vertices as possible by deciding in each round which vertices to protect, without knowing in advance when and how many firefighters will become available in the future. It is known that the online firefighting is 2 2 -competitive on trees [ 2 ] , which suggests that the problem is relatively easy on trees. We extend the study to graphs containing cycles. We first show that the presence of cycles gives a strong advantage to the adversary: cycles create situations where the algorithm and the optimal solution operate on different game states, and the adversary can exploit the uncertainty in the firefighter sequence to trap the algorithm. Specifically, we prove that even on a tadpole graph (a cycle with a tail path), no deterministic online algorithm achieves a competitive ratio better than Ω ⁡ ( n ) \Omega(\sqrt{n}) , where n n is the number of vertices. We then propose an O ⁡ ( n ) O(\sqrt{n}) -competitive algorithm for 1 1 -almost trees, which contain at most one cycle and generalize tadpole graphs. We further generalize this algorithm to cactus graphs, in which multiple cycles may appear, but no two share more than one vertex, and show that the online firefighting problem on cactus graphs remains O ⁡ ( n ) O(\sqrt{n}) -competitive. Finally, since cactus graphs have treewidth at most 2 2 , we study a variant where firefighters are released in pairs, that is, each round an even number of firefighters is available. Surprisingly, in this setting, the competitive complexity is significantly reduced, and we prove that the problem is at most 3 3 -competitive. The main technical challenges lie in both algorithm design and analysis, since the algorithm and the optimal solution may break different cycles and thus operate on different residual graphs. To overcome this difficulty, we design a charging framework that carefully partitions the vertices saved by the optimal solution and charges them to the vertices saved by the algorithm. Specifically, the charging scheme is carefully constructed to ensure that each vertex saved by the algorithm is charged at most a constant number of times. Department of Information and Computing Sciences, Utrecht University, The NetherlandsDepartment of Information and Computing Sciences, Utrecht University, The [email protected]://orcid.org/0009-0000-5517-6095 Department of Information and Computing Sciences, Utrecht University, The [email protected]://orcid.org/0000-0002-0194-9360 ccs Theory of computation → Online algorithms keywords Firefighting problem, Online algorithms, Cactus graphs, 1-almost trees † † runningauthor: M. Hugen, B. Krekelberg and A. H. H. Liu † † copyright: Max Hugen, Bob Krekelberg and Alison Hsiang-Hsuan Liu † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The online firefighting game proceeds in rounds as follows. Initially, the algorithm is given a graph with a designated fire source. At the beginning of each round, the algorithm is informed of the number of firefighters available in that round and assigns them to protect unburned vertices. Subsequently, every unprotected neighbor of a burning vertex catches fire, concluding the round. The online algorithm aims to maximize the number of saved vertices, without knowing in advance how many firefighters will be available in future rounds. We evaluate the performance of an online algorithm for the firefighting game using competitive analysis . An algorithm ALG is c -competitive if \sup_{\mathcal{I}}\frac{\text{OPT}(\mathcal{I})}{\text{ALG}(\mathcal{I})}\leq c , where \text{ALG}(\mathcal{I}) denotes the number of vertices saved by ALG on instance \mathcal{I} , and \text{OPT}(\mathcal{I}) denotes the maximum number of vertices that can be saved on \mathcal{I} . From the complexity perspective, the competitive ratio of an online problem is defined as the infimum competitive ratio achievable by any online algorithm for the problem. Introduced by Hartnell in 1995 [ 5 ] , the firefighter problem can be seen more generally as a model for a threat spreading through a network. For example, the problems of minimizing the spread of misinformation or threats in social or computer networks, immunizing a population against a virus, and reducing the spread of an invasive species in an ecosystem are also captured by this model. The firefighting problem is known to be a computationally hard problem. Even for restricted graph classes such as bipartite graphs [ 7 ] and even for trees of maximum degree 3 [ 4 ] , the problem is shown to be NP-hard. On the positive side, several approximation algorithms are known for the firefighting problem. For example, the greedy algorithm is shown to be a \frac{1}{2} -approximation on trees. [ 6 ] , and also, there also exists a polynomial time approximation scheme for the firefighting problem on trees. [ 1 ] . The online variant of the firefighting problem was introduced by Coupechoux et al. in 2019 [ 2 ] . They showed that the greedy algorithm on trees in the online version of the problem is 2 -competitive and optimal. Also, in the fractional version of the problem, in which a fraction of a firefighter can be assigned to a vertex to partially protect it, Coupechoux et al. [ 2 ] show that the greedy algorithm is 2 -competitive on trees. Furthermore, in the special case where the number of firefighters is bounded by 2 , Coupechoux et al. [ 2 ] propose a \phi -competitive algorithm on trees, where \phi is the golden ratio. Later, Demange et al. [ 3 ] investigated sufficient conditions for online containment of fires on infinite grid graphs. They show that for an algorithm to contain the fire, there needs to exist a turn t such that the sum of firefighters released until (including) turn t is at least 16t . In this work, we study the competitive complexity of the online firefighting game. It is known that the game is 2 -competitive on trees, indicating that the problem is relatively simple in this setting. This raises the question of how the competitive complexity evolves on broader classes of graphs. Surprisingly, we find that with the addition of a single extra edge to a tree, the problem is no longer constant-competitive. Theorem 1 . No deterministic online algorithm can achieve o(\sqrt{n}) -competitiveness for the online firefighting problem on tadpole graphs. Proof. Consider an arbitrary deterministic online algorithm ALG . Let the input graph G be an (\alpha+1,\beta+1) -tadpole graph, consisting of a cycle of \alpha+1 vertices and a path of \beta+1 vertices joined at a common vertex r , where r is the unique degree- 3 vertex of G . In the first

Read the complete text