APX-Hardness and Approximation for the k-Burning Number Problem
share
Consider an information diffusion process on a graph G that starts with k>0 burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps b_k(G) such that all the vertices can be burned within b_k(G) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k. In this paper we prove that computing k-burning number is APX-hard, for any fixed constant k. We then give an O((n+m)log n)-time 3-approximation algorithm for computing k-burning number, for any k≥ 1, where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.
READ FULL TEXT