The severity of wildfires can be mitigated using preventive measures like the construction of firebreaks, which are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location . A land of unknown size is modeled as an infinite undirected graph in which the vertices correspond to areas subject to fire and edges represent fire propagation from one area to another. A firebreak construction is modeled as removing the edge between two vertices. The number of firebreaks that can be installed depends on budget constraints. We assume that a fire ignites in a subset of vertices and propagates to the neighbors. The goal is to select a subset of edges to remove in order to contain the fire and avoid burning an infinite part of the graph. We prove that Infinite Windy Firebreak Location is coNP-complete in restricted cases, and we address some polynomial cases. We show that Infinite Windy Firebreak Location polynomially reduces to Min Cut for certain classes of graphs like infinite grid graphs and polyomino-grids.

In this paper we consider an online version of different colouring problems in overlap graphs, motivated by some stacking problems. The instance is a system of time intervals presented in non-decreasing order of the left endpoint. We consider the usual colouring problem as well as b-bounded colouring (colour class have a maximum capacity b) and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can intersect. For all these versions we obtain a logarithmic competitive ratio w.r.t. the maximum ratio of interval lengths while the best known ratio for the usual colouring was linear. To our knowledge it is the first time the other variants are considered in online overlap graphs. Moreover, in the offline case, a pre-processing allows us to deduce a logarithmic approximation ratio w.r.t. the maximum number of pairwise disjoint intervals in the system. Our method is based on a partition of the overlap graph into permutation graphs, leading to a competitive-preserving reduction of the problem in overlap graphs to the same problem in permutation graphs. We think that this new partition problem by itself is of interest for future work.

We consider online versions of different colouring problems in interval overlap graphs, motivated by stacking problems. An instance is a system of time intervals presented in non-decreasing order of the left endpoints. We consider the usual colouring problem as well as b -bounded colouring and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can include the same element. For these versions, we obtain a logarithmic competitive ratio with respect to the maximum ratio of interval lengths. The best known ratio for the usual colouring was linear, and to our knowledge other variants have not been considered. Moreover, pre-processing allows us to deduce approximation results in the offline case. Our method is based on a partition of the overlap graph into permutation graphs, leading to a competitive-preserving reduction of the problem in overlap graphs to the same problem in permutation graphs. This new partition problem by itself is of interest for future work.

We consider a generalisation of MIN WEIGHTED VERTEX COVER motivated by a problem in wildfire prevention. The problem is defined for a fixed number of time periods and we have to choose, at each period, some vertices to be deleted such that we never have two adjacent remaining vertices. The specificity is that whenever a vertex is deleted it reappears after a given number of periods. Consequently we may need to delete a single vertex several times. The objective is to minimise the total weight (cost) of deleted vertices. The considered application motivates the case of planar graphs. While similar problems have been mainly solved using mixed integer linear models (MIP) we investigate a graph approach that allows to take into account the structure of the underlying graph. We use a reduction to the usual MIN WEIGHTED VERTEX COVER to devise efficient approximation algorithms and to raise some polynomial classes. Copyright