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

dmtcs:2559 - Discrete Mathematics & Theoretical Computer Science, September 26, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-5
Irreversible 2-conversion set in graphs of bounded degreeArticle

Authors: Jan Kynčl ORCID; Bernard Lidický ; Tomáš Vyskočil

    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.


    Volume: Vol. 19 no. 3
    Section: Graph Theory
    Published on: September 26, 2017
    Accepted on: September 14, 2017
    Submitted on: June 8, 2017
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,Mathematics - Combinatorics,05C85, 05C07, 05B35,G.2.2
    Funding:
      Source : OpenAIRE Graph
    • Coloring-related problems for graphs and hypergraphs with degree restrictions; Funder: National Science Foundation; Code: 1266016

    Consultation statistics

    This page has been seen 730 times.
    This article's PDF has been downloaded 311 times.