Burning Graphs Through Farthest-First Traversal

Graph burning is a process to determine the spreading of information in a graph. If a sequence of vertices burns all the vertices of a graph by following the graph burning process, then such a sequence is known as a burning sequence. The graph burning problem consists in finding a minimum length burning sequence for a given graph. The solution to this NP-hard combinatorial optimization problem helps quantify a graph&#x2019;s vulnerability to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over arbitrary graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in <inline-formula> <tex-math notation="LaTeX">$O(n^{3})$ </tex-math></inline-formula> steps and has a tight approximation factor of <inline-formula> <tex-math notation="LaTeX">$3-2/b(G)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$b(G)$ </tex-math></inline-formula> is the size of an optimal solution. The main attribute of BFF is that it has a better approximation factor than the state-of-the-art approximation algorithms for arbitrary graphs, which report an approximation factor of 3. Despite being simple, BFF proved practical when tested over some benchmark datasets.