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

This page has been seen 97 times.

This article's PDF has been downloaded 42 times.