The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify the vulnerability of a graph to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over general graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in $O(n^3)$ steps and has an approximation factor of $3-2/b(G)$, where $b(G)$ is the size of an optimal solution. Despite its simplicity, BFF tends to generate near-optimal solutions when tested over some benchmark datasets; in fact, it returns similar solutions to those returned by much more elaborated heuristics from the literature.

翻译：图形燃烧问题是一个NP硬的组合优化问题, 有助于量化图表易传染的脆弱性。 本文在一般图表中引入了一个简单的最远的、 最远的、 最前沿的近距离近似算法。 我们将此建议称为燃烧最远第一( BFF) 算法。 BFF 以$O(n) 3 步数运行, 近似系数为 3 2/b( G) 美元, 其中$b( G) 是最佳解决方案的大小 。 尽管它简单, BFF 在对某些基准数据集进行测试时往往产生近乎最佳的解决方案 ; 事实上, 它会返回由文献中更精细的重金字返回的类似解决方案 。