Irreversible 2-conversion set in graphs of bounded degree

dc.contributor.author Kyncl, Jan
dc.contributor.author Lidicky, Bernard
dc.contributor.author Lidicky, Bernard
dc.contributor.author Vyskocil, Tomas
dc.contributor.department Mathematics
dc.date 2018-10-29T21:14:07.000
dc.date.accessioned 2020-06-30T06:00:14Z
dc.date.available 2020-06-30T06:00:14Z
dc.date.copyright Sun Jan 01 00:00:00 UTC 2017
dc.date.issued 2017-09-26
dc.description.abstract <p>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.</p>
dc.description.comments <p>This article is published as Vyskočil, Tomáš, Bernard Lidický, and Jan Kynčl. "Irreversible 2-conversion set in graphs of bounded degree." <em>Discrete Mathematics & Theoretical Computer Science</em> 19 (2017): 5. doi: <a href="http://dx.doi.org/10.23638/DMTCS-19-3-5" target="_blank">10.23638/DMTCS-19-3-5</a>.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/187/
dc.identifier.articleid 1195
dc.identifier.contextkey 13194045
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/187
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54576
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/187/2017_Lidicky_IrreversibleConversion.pdf|||Fri Jan 14 21:45:53 UTC 2022
dc.source.uri 10.23638/DMTCS-19-3-5
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.disciplines Mathematics
dc.subject.keywords irreversible k-conversion process
dc.subject.keywords spread of infection
dc.subject.keywords bootstrap percolation
dc.subject.keywords NP-complete problem
dc.subject.keywords matroid parity problem
dc.subject.keywords toroidal grid
dc.title Irreversible 2-conversion set in graphs of bounded degree
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication a1d8f5ab-9124-4104-981c-8ba1e426e3ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
2017_Lidicky_IrreversibleConversion.pdf
Size:
474.95 KB
Format:
Adobe Portable Document Format
Description:
Collections