Upper bounds and approximation results for the k -slow burning problem

Discrete Applied Mathematics, vol. 363, pp. 88–104

Abstract

k -slow burning is a model for contagion in social networks. In this model, given an undirected graph G in every time step , first every burning vertex spreads the fire to up to k of its neighbours, before second one additional source of fire is ignited. The k -slow burning number, denoted by b s ( k , G ) , is the minimum number of time steps needed until the whole graph is burning. This model can be seen as a combination of the classic graph burning problem and the much older ( k -)broadcasting problem. We prove NP -hardness of the k -slow burning problem for every fixed k on path forests, spider graphs and most notably the class of graphs of radius 1, where normal graph burning is solvable in polynomial time. Furthermore, we show that among all connected graphs on n vertices, the k -slow burning number of the star graph, b s ( k , S n − 1 ) , is maximal for k ∈ { 1 , 2 } and asymptotically maximal for fixed k ≥ 3 . This observation motivates a generalisation of the burning number conjecture for k -slow burning. Finally, we give a 3 / 2 -approximation for the k -slow burning problem on path forests and a 2-approximation on trees .

Authors 3

1. Michaela Hiller Aachen Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Discrete Optimization, RWTH Aachen University, Germany

2. Arie M. C. A. Koster Aachen Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Discrete Optimization, RWTH Aachen University, Germany

3. Philipp Pabst corresponding Aachen Chair of Management Science

   RWTH Aachen University

   Affiliation as printed

   Chair of Management Science, RWTH Aachen University, Germany