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. Many of its theoretical properties across different graph families have been thoroughly explored, and numerous interesting variants have been proposed. This paper reports novel mathematical programs for the optimization version of the classical GBP. Among the presented programs are a Mixed-Integer Linear Program (MILP), a Constraint Satisfaction Problem (CSP), two Integer Linear Programs (ILP), and two Quadratic Unconstrained Binary Optimization (QUBO) problems. Most optimization solvers can handle these, being QUBO problems of a capital interest in quantum computing. The primary aim of this paper is to gain a comprehensive understanding of the GBP by examining its different formulations. Compared to other mathematical programs from the literature, the ones presented here are conceptually simpler and involve fewer variables. These make them more practical for finding optimal solutions using optimization algorithms and solvers, as we show by solving some instances with millions of vertices in just a few minutes.

翻译：图燃烧问题（GBP）是一种组合优化问题，近年来作为量化图对传播过程的脆弱性工具而受到关注。尽管其基于简单的传播模型，其判定版本属于NP完全问题，优化版本属于NP难问题。该问题在不同图族中的理论性质已得到深入探索，并衍生出多种有趣的变体。本文针对经典GBP的优化版本提出了新的数学规划模型，包括混合整数线性规划（MILP）、约束满足问题（CSP）、两种整数线性规划（ILP）以及两种二次无约束二进制优化（QUBO）问题。这些模型可被大多数优化求解器处理，其中QUBO问题对量子计算具有重要价值。本文旨在通过分析不同建模形式深化对GBP的理解。与现有文献中的数学规划相比，本文提出的模型在概念上更简洁且变量更少，从而提升了优化算法与求解器的实用性——我们通过实验证明，可在数分钟内求解包含数百万顶点的算例。