Dominance and symmetry-breaking rules for the Graph Burning Problem

The Graph Burning Problem (GBP) is an NP-hard combinatorial optimization problem that models the spread of influence or contagion in a network through a metaphor where a fire spreads through a graph's vertices. At each time step, an unburned vertex is ignited and burned vertices spread their fire to their immediate neighbors. The minimum number of steps required to burn all vertices defines the graph’s burning number. Litterature provides integer linear programs for the problem, but those struggle to converge as the graph size increases, making search-space reduction essential for improving performances. In this work, we investigate connections between GBP and the Dominating Set Problem to derive a new formulation. We further enhance the model with dominance rules and symmetry-breaking techniques to reduce redundant exploration and accelerate solution times. Additionally, we propose a perturbed objective function together with a pruning rule tailored to the perturbed model, leading to further computational improvements.