Irreversible conversion processes with deadlines
Given a graph G , a deadline td(u) t d ( 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 = ( c 0 , c 1 ,  ) of 0/1-labelings ci c i of the vertices of G  such that for every t?N t ? N , we have ct(u)=1 c t ( u ) = 1 if and only if either ct?1(u)=1 c t ? 1 ( u ) = 1 or at least f(u,t?1) f ( u , t ? 1 ) neighbors v of u  satisfy ct?1(v)=1 c t ? 1 ( v ) = 1 . The sequence C C models the spreading of a property/commodity within a network and it is said to converge to 1 on time, if ctd(u)(u)=1 c t d ( 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) t d ( u ) . We study the smallest number irr(G,td,f) irr ( G , t d , f ) of vertices u  with initial label c0(u) c 0 ( u ) equal to 1 that result in a sequence C C converging to 1 on time. If G  is a forest or a clique, we present efficient algorithms computing irr(G,td,f) irr ( G , t d , f ) . Furthermore, we prove lower and upper bounds relying on counting and probabilistic arguments. For special choices of td t d and f , the parameter irr(G,td,f) irr ( G , t d , f ) coincides with well-known graph parameters related to domination and independence in graphs.
domination independence iterative graph process dynamic monopoly