Article ID Journal Published Year Pages File Type
6875700 Theoretical Computer Science 2018 17 Pages PDF
Abstract
In 2-neighborhood bootstrap percolation on a graph G, given an initially infected set of vertices of G, an infection spreads according to the following deterministic rule: once a vertex of G is infected, it remains infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbors becomes infected. Percolation occurs if eventually every vertex is infected. The maximum time t(G) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2015, it was proved [8] that deciding whether t(G)≥k is polynomial time solvable for k=2, but is NP-Complete for k=4 and, if the problem is restricted to bipartite graphs, it is NP-Complete for k=7. In this paper, we solve the open questions. We obtain an O(mn5)-time algorithm to decide whether t(G)≥3. For bipartite graphs, we obtain an O(mn3)-time algorithm to decide whether t(G)≥3, an O(m2n9)-time algorithm to decide whether t(G)≥4 and we prove that t(G)≥5 is NP-Complete.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,