Irreversible 2-conversion set in graphs of bounded degree

Abstract

An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such that the irreversible $k$-threshold process starting with $S$ black eventually changes all vertices of $G$ to black. We show that deciding the existence of an irreversible 2-conversion set of a given size is NP-complete, even for graphs of maximum degree 4, which answers a question of Dreyer and Roberts. Conversely, we show that for graphs of maximum degree 3, the minimum size of an irreversible 2-conversion set can be computed in polynomial time. Moreover, we find an optimal irreversible 3-conversion set for the toroidal grid, simplifying constructions of Pike and Zou.

18 pages, 12 figures; journal version

References in corpus (1)

• An Improved Upper Bound for Bootstrap Percolation in All Dimensions

Cited by in corpus (3)

• Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets
• On the Complexity of Target Set Selection in Simple Geometric Networks
• On Reconfigurability of Target Sets