Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades

Consider the following reversible cascade on a simple directed graph G=(V,E). In round zero, a set of vertices, called the seeds, are active. In round [email protected]?Z^+, a vertex [email protected]?V is activated (deactivated) if at least (resp., fewer than) @f(v) of its in-neighbors are active in round k-1, where @f:V->N. An irreversible cascade is defined similarly except that active vertices cannot be deactivated. Two specific candidates for the threshold function @f are @f"m"a"j"("v")^s^t^r^i^c^[email protected]?(deg^-(v)+1)/[email protected]? and @f"@r(v)[email protected][email protected]@?deg^-(v)@?, where deg^-(v) denotes the indegree of [email protected]?V and @[email protected]?(0,1]. An irreversible dynamic monopoly is a set of seeds that leads all vertices to activation after finitely many rounds of the irreversible cascade with @[email protected]"m"a"j^s^t^r^i^c^t. A set of vertices, S, is said to be convergent if no vertex will ever change its state, from active to inactive or vice versa, once the set of active vertices equals S. This paper shows that an irreversible dynamic monopoly of size at most @?|V|/[email protected]? can be found in polynomial (in |V|) time if G is strongly connected. Furthermore, we show that for any constant @e>0, all @[email protected]?(0,1], @[email protected]"@r, [email protected]?[([email protected])(ln(e/@r))/n,1] and with probability 1-n^-^@W^(^1^), every convergent set of the Erdos-Renyi random graph G(n,p) has size O(@[email protected]@?) or n-O(@[email protected]@?). Our result on convergent sets holds for both the reversible and irreversible cascades.