Triggering cascades on strongly connected directed graphs

Consider the following process of activation on a strongly connected directed graph G(V,E)G(V,E) with threshold function ϕ:V→Nϕ:V→N. In round zero, a set of vertices, called the seeds, are active. Thereafter, a vertex v∈Vv∈V is activated in a round if it has at least ϕ(v)ϕ(v) active in-neighbors in the previous round. Once a vertex is activated, it remains active. Sets of seeds activating all vertices after a finite number of rounds are known in the literature as irreversible dynamic monopolies (a.k.a. perfect target sets) corresponding to (G,ϕ)(G,ϕ). With ϕ(v)=⌈ρdeg−(v)⌉ for all v∈Vv∈V, where deg−(v)deg−(v) denotes the indegree of v   and ρ∈(0,1], this paper proves the existence of an irreversible dynamic monopoly of size no more than max⁡{4.92ρ|V|,1}.