The maximum time of 2-neighbour bootstrap percolation: Algorithmic aspects

In 2-neighbourhood bootstrap percolation on a graph G , an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. In this paper, we are interested to calculate the maximal time t ( G ) the process can take, in terms of the number of times the interval function is applied, to eventually infect the entire vertex set. We prove that the problem of deciding if t ( G ) ? k is NP-complete for: (a) fixed k ? 4 ; (b) bipartite graphs and fixed k ? 7 ; and (c) planar graphs. Moreover, we obtain linear and polynomial time algorithms for trees and chordal graphs, respectively.