Abstract
A Row Generation Algorithm for Finding Optimal Burning Sequences
of Large Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024).
Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp.
94:1-94:17, 2024 We propose an exact algorithm for the Graph Burning Problem ($\texttt{GBP}$),
an NP-hard optimization problem that models the spread of influence on social
networks. Given a graph $G$ with vertex set $V$, the objective is to find a
sequence of $k$ vertices in $V$, namely, $v_1, v_2, \dots, v_k$, such that $k$
is minimum and $\bigcup_{i = 1}^{k} \{u\! \in\! V\! : d(u, v_i) \leq k - i\} =
V$, where $d(u,v)$ denotes the distance between $u$ and $v$. We formulate the
problem as a set covering integer programming model and design a row generation
algorithm for the $\texttt{GBP}$. Our method exploits the fact that a very
small number of covering constraints is often sufficient for solving the
integer model, allowing the corresponding rows to be generated on demand. To
date, the most efficient exact algorithm for the $\texttt{GBP}$, denoted here
by $\texttt{GDCA}$, is able to obtain optimal solutions for graphs with up to
14,000 vertices within two hours of execution. In comparison, our algorithm
finds provably optimal solutions approximately 236 times faster, on average,
than $\texttt{GDCA}$. For larger graphs, memory space becomes a limiting factor
for $\texttt{GDCA}$. Our algorithm, however, solves real-world instances with
almost 200,000 vertices in less than 35 seconds, increasing the size of graphs
for which optimal solutions are known by a factor of 14.