Irreversible 2-conversion set in graphs of bounded degree

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2017-09, Vol.19 no. 3 (Graph Theory)
Main Authors: Jan Kynčl, Bernard Lidický, Tomáš Vyskočil
Format: Article
Language:English
Subjects:
05c85, 05c07, 05b35
computer science - computational complexity
computer science - discrete mathematics
g.2.2
mathematics - combinatorics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
DOI:10.23638/DMTCS-19-3-5