Advertisement
Published in:
2014 | OriginalPaper | Chapter
The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
Authors : Thiago Marcilon, Samuel Nascimento, Rudini Sampaio
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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. The maximum time \(t(G)\) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved [7] that deciding if \(t(G)\ge k\) is polynomial time solvable for \(k=2\), but is NP-Complete for \(k=4\) and is NP-Complete if the graph is bipartite and \(k=7\). In this paper, we solve the open questions. Let \(n = |V(G)|\) and \(m = |E(G)|\). We obtain an \(\varTheta (m n^5)\)-time algorithm to decide if \(t(G)\ge 3\) in general graphs. In bipartite graphs, we obtain an \(\varTheta (m n^3)\)-time algorithm to decide if \(t(G)\ge 3\) and an \(O(m n^{13})\)-time algorithm to decide if \(t(G)\ge 4\). We also prove that deciding if \(t(G)\ge 5\) is NP-Complete in bipartite graphs.