{"id":"arxiv/2606.10966","url":"https://arxiv.org/abs/2606.10966","tags":["math.OC","math.CO"],"score":0,"title":"Dominance and symmetry-breaking rules for the Graph Burning Problem","domain":"math.OC","source":"arxiv","authors":["Nice Prado","Rafael Colares"],"reviews":0,"subject":"math.OC","summary":"The Graph Burning Problem (GBP) is a NP-Hard combinatorial optimization problem that models the propagation of influence or contagion in a network. The propagation is represented through the metaphor of a fire spreading through the vertices of a graph. A burning process takes place in a series of discrete time-steps. At each time step, the burning process is characterized by a propagation (where burned nodes spread the fire to their neighbors), and an ignition (where one additional unburned node is chosen to become burned). The minimum number of steps required to burn all vertices of a graph…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-09","reactions":{}}