Graph Burning: An Overview of Compact Mathematical Programs

The Graph Burning Problem (GBP) is a combinatorial optimization problem that has gained relevance as a tool for quantifying a graph’s vulnerability to contagion. Although it is based on a very simple propagation model, its decision version is NP-complete and its optimization version is NP-hard. This paper introduces novel mathematical programs for the GBP. Among the introduced programs are a Mixed-Integer Linear Program (MILP), a Constraint Satisfaction Problem (CSP), two Integer Linear Programs (ILPs), and two Quadratic Unconstrained Binary Optimization (QUBO) problems. Most optimization solvers can handle these, with QUBO problems being of capital interest in quantum computing. Nonetheless, the primary objective of this paper is not to solve instances of the GBP, but rather to deepen our understanding of it by identifying and examining what we believe to be its simplest mathematical formulations, that is, models that use as few variables and constraints as possible (compact mathematical programs). We believe that this collection of programs can provide ideas for modeling variants and related problems. As a marginal result, one of the proposed ILPs, equipped with a row generation technique, allowed a commercial solver to find optimal solutions for some of the largest and most challenging instances for the GBP.