Irreversible 2-conversion set in graphs of bounded degree
Is Version Of
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 the vertices of 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.
This article is published as Vyskočil, Tomáš, Bernard Lidický, and Jan Kynčl. "Irreversible 2-conversion set in graphs of bounded degree." Discrete Mathematics & Theoretical Computer Science 19 (2017): 5. doi: 10.23638/DMTCS-19-3-5.