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
1 - 1 of 1
No Thumbnail Available
- Name:
- 2017_Lidicky_IrreversibleConversion.pdf
- Size:
- 474.95 KB
- Format:
- Adobe Portable Document Format
- Description: