Graph Burning: An Overview of Compact Mathematical Programs
Mathematics · 17.03.2026 · 14 (6) · 1011
DOI: 10.3390/math14061011 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 17.03.2026. Verfasst von Lourdes Beatriz Cajica-Maceda und 3 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Cajica-Maceda, L. B., Chaurra-Gutiérrez, F. A., Pérez-Sansalvador, J. C., & García-Díaz, J. (2026). Graph Burning: An Overview of Compact Mathematical Programs. Mathematics, 14(6), 1011. https://doi.org/10.3390/math14061011
Vancouver
Cajica-Maceda LB, Chaurra-Gutiérrez FA, Pérez-Sansalvador JC, García-Díaz J. Graph Burning: An Overview of Compact Mathematical Programs. Mathematics. 2026;14(6):1011. doi:10.3390/math14061011
BibTeX
@article{CajicaMaceda2026,
author = {Cajica-Maceda, Lourdes Beatriz and Chaurra-Gutiérrez, Freddy Alejandro and Pérez-Sansalvador, Julio César and García-Díaz, Jesús},
title = {Graph Burning: An Overview of Compact Mathematical Programs},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {6},
pages = {1011},
doi = {10.3390/math14061011}
}
EUVIMED