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.

This work examines a strongly NP-hard routing problem on trees, in which multiple servers need to serve a given set of requests (on vertices), where the routes of the servers start from a common source and end at their respective terminals. Each server can travel free of cost on its source-to-terminal path but has to pay for travel on other edges. The objective is to minimize the maximum cost over all servers. As the servers may pay different costs for traveling through a common edge, balancing the loads of the servers can be difficult. We propose a polynomial-time 4-approximation algorithm that applies the parametric pruning framework but consists of two phases. The first phase of the algorithm partitions the requests into packets, and the second phase of the algorithm assigns the packets to the servers. Unlike the standard parametric pruning techniques, the challenge of our algorithm design and analysis is to harmoniously relate the quality of the partition in the first phase, the balances of the servers' loads in the second phase, and the hypothetical optimal values of the framework. For the problem in general graphs, we show that there is no algorithm better than 2-approximate unless P = NP. The problem is a generalization of unrelated machine scheduling and other classic scheduling problems. It also models scheduling problems where the job processing times depend on the machine serving the job and the other jobs served by that machine. This modeling provides a framework that physicalizes scheduling problems through the graph’s point of view.