Irreversible conversion of graphs

详细信息    查看全文

• 作者：Carmen C. Centeno^a ; ^{carmen@cos.ufrj.br"" rel=""nofollow} ; Mitre C. Dourado^a ; ^{mitre@nce.ufrj.br"" rel=""nofollow} ; Lucia Draque Penso^b ; ^{lucia.penso@uni-ulm.de"" rel=""nofollow} ; Dieter Rautenbach^b ; ^{dieter.rautenbach@uni-ulm.de"" rel=""nofollow} ; ^{Dieter.Rautenbach@tu-ilmenau.de"" rel=""nofollow} ; Jayme L. Szwarcfiter^a ; ^{jayme@nce.ufrj.br"" rel=""nofollow}
• 关键词：Irreversible threshold process ; Local majority process ; Fault propagation ; Spread of disease ; Dynamic monopoly ; Catastrophic fault pattern
• 刊名：Theoretical Computer Science
• 出版年：2011
• 出版时间：1 July 2011
• 年：2011
• 卷：412
• 期：29
• 页码：3693-3700
• 全文大小：335 K

文摘

Given a graph G, a function , and an initial 0/1-vertex-labelling c₁:V(G)→{0,1}, we study an iterative 0/1-vertex-labelling process on G where in each round every vertex v never changes its label from 1 to 0, and changes its label from 0 to 1 if at least f(v) neighbours have label 1. Such processes model opinion/disease spreading or fault propagation and have been studied under names such as irreversible threshold/majority processes in a large variety of contexts. Our contributions concern computational aspects related to the minimum cardinality of sets of vertices with initial label 1 such that during the process on G all vertices eventually change their label to 1. Such sets are known as irreversible conversion sets, dynamic irreversible monopolies, or catastrophic fault patterns. Answering a question posed by Dreyer and Roberts [P.A. Dreyer Jr., F.S. Roberts, Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math. 157 (2009) 1615–1627], we prove a hardness result for where f(v)=2 for every vV(G). Furthermore, we describe a general reduction principle for , which leads to efficient algorithms for graphs with simply structured blocks such as trees and chordal graphs.