Reversible iterative graph processes

Given a graph G, a function f:V(G)→Z, and an initial 0/1-vertex-labelling c1:V(G)→{0,1}, we study an iterative 0/1-vertex-labelling process on G where in each round every vertex v changes its label if and only if at least f(v) neighbours have a different label. For special choices of the values of f, such processes model consensus issues and have been studied under names such as local majority processes or iterative polling processes in a large variety of contexts especially in distributed computing. 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 dynamic monopolies or dynamos for short. We establish a hardness result and describe efficient algorithms for restricted instances on paths and cycles.