Irreversible 2-conversion set in graphs of bounded degree
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3
Voir la notice de l'article provenant de la source Episciences
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.
@article{DMTCS_2017_19_3_a5,
author = {Kyn\v{c}l, Jan and Lidick\'y, Bernard and Vysko\v{c}il, Tom\'a\v{s}},
title = {Irreversible 2-conversion set in graphs of bounded degree},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {19},
number = {3},
year = {2017-2018},
doi = {10.23638/DMTCS-19-3-5},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/}
}
TY - JOUR AU - Kynčl, Jan AU - Lidický, Bernard AU - Vyskočil, Tomáš TI - Irreversible 2-conversion set in graphs of bounded degree JO - Discrete mathematics & theoretical computer science PY - 2017-2018 VL - 19 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/ DO - 10.23638/DMTCS-19-3-5 LA - en ID - DMTCS_2017_19_3_a5 ER -
%0 Journal Article %A Kynčl, Jan %A Lidický, Bernard %A Vyskočil, Tomáš %T Irreversible 2-conversion set in graphs of bounded degree %J Discrete mathematics & theoretical computer science %D 2017-2018 %V 19 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-5/ %R 10.23638/DMTCS-19-3-5 %G en %F DMTCS_2017_19_3_a5
Kynčl, Jan; Lidický, Bernard; Vyskočil, Tomáš. Irreversible 2-conversion set in graphs of bounded degree. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi: 10.23638/DMTCS-19-3-5
Cité par Sources :