2018/02/12 by Stéphane Bessy, Bessy, Stéphane, Stefan Ehard +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1802.03935
arxiv created 2018/02/12 · arxiv updated 2018/02/13
For a graph G and an integer-valued threshold function τ on its vertex set, a dynamic monopoly is a set of vertices of G such that iteratively adding to it vertices u of G that have at least τ(u) neighbors in it eventually yields the vertex set of G. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.