Campus Units
Mathematics
Document Type
Article
Publication Version
Published Version
Publication Date
9-26-2017
Journal or Book Title
Discrete Mathematics & Theoretical Computer Science
Volume
19
Issue
3
First Page
5
DOI
10.23638/DMTCS-19-3-5
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 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.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Copyright Owner
The Authors
Copyright Date
2017
Language
en
File Format
application/pdf
Recommended Citation
Kyncl, Jan; Lidicky, Bernard; and Vyskocil, Tomas, "Irreversible 2-conversion set in graphs of bounded degree" (2017). Mathematics Publications. 187.
https://lib.dr.iastate.edu/math_pubs/187
Comments
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.