Irreversible 2-conversion set in graphs of bounded degree

Thumbnail Image
Date
2017-09-26
Authors
Kyncl, Jan
Lidicky, Bernard
Vyskocil, Tomas
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

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.

Description
Keywords
Citation
DOI
Copyright
Sun Jan 01 00:00:00 UTC 2017
Collections