Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875700 | Theoretical Computer Science | 2018 | 17 Pages |
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
Thiago Marcilon, Rudini Sampaio,