On the approximability of the burning number

Abstract

The burning number of a graph $G$ is the smallest number $b$ such that the vertices of $G$ can be covered by balls of radii $0,1,\dots ,b-1$. As computing the burning number of a graph is known to be NP-hard, even on trees, it is natural to consider polynomial time approximation algorithms for the quantity. The best known approximation factor in the literature is $3$ for general graphs and $2$ for trees. In this note we give a $2/(1-e^{-2})+\epsilon =2.313\dots$-approximation algorithm for the burning number of general graphs, and a PTAS for the burning number of trees and forests. Moreover, we show that computing a $(\frac{5}{3}-\epsilon )$-approximation of the burning number of a general graph $G$ is NP-hard.

7 pages, no figures. Comments are welcome!