Algorithms and Complexity of Graph Infection Problems

A reversible process over a graph G=(V,E) is an iterative process such that, given a threshold function f:V(G) → N and an initial labeling c0 : V(G) → {0,1}, each vertex v changes its label if and only if it has at least f(v) neighbors with the opposite label, at each time step t belonging to the natural ones. We study the problem of determining the minimum number r_f(G) of vertices with initial label 1, such that all vertices reach label 1 definitively, in a finite number of time steps. We study the computational complexity of determining rf(G) for some classes of graphs.