Irreversible conversion processes with deadlines

Given a graph G  , a deadline td(u)td(u) and a time-dependent threshold f(u,t)f(u,t) for every vertex u of G  , we study sequences C=(c0,c1,…)C=(c0,c1,…) of 0/1-labelings cici of the vertices of G   such that for every t∈Nt∈N, we have ct(u)=1ct(u)=1 if and only if either ct−1(u)=1ct−1(u)=1 or at least f(u,t−1)f(u,t−1) neighbors v of u   satisfy ct−1(v)=1ct−1(v)=1. The sequence CC models the spreading of a property/commodity within a network and it is said to converge to 1 on time, if ctd(u)(u)=1ctd(u)(u)=1 for every vertex u of G, that is, if every vertex u   has the spreading property/received the spreading good by time td(u)td(u).We study the smallest number irr(G,td,f)irr(G,td,f) of vertices u   with initial label c0(u)c0(u) equal to 1 that result in a sequence CC converging to 1 on time. If G   is a forest or a clique, we present efficient algorithms computing irr(G,td,f)irr(G,td,f). Furthermore, we prove lower and upper bounds relying on counting and probabilistic arguments. For special choices of tdtd and f  , the parameter irr(G,td,f)irr(G,td,f) coincides with well-known graph parameters related to domination and independence in graphs.