Kynčl, Jan and Lidický, Bernard and Vyskočil, Tomáš - Irreversible 2-conversion set in graphs of bounded degree

dmtcs:3952 - Discrete Mathematics & Theoretical Computer Science, September 26, 2017, Vol 19 no. 3
Irreversible 2-conversion set in graphs of bounded degree

Authors: Kynčl, Jan and Lidický, Bernard and Vyskočil, Tomáš

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.


Source : oai:arXiv.org:1412.4188
Volume: Vol 19 no. 3
Section: Graph Theory
Published on: September 26, 2017
Submitted on: June 8, 2017
Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,Mathematics - Combinatorics,05C85, 05C07, 05B35,G.2.2


Share

Browsing statistics

This page has been seen 35 times.
This article's PDF has been downloaded 11 times.