Latency-bounded target set selection in social networks ?
Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a graph G=(V,E) G = ( V , E ) , integer values t(v) t ( v ) for each vertex v (thresholds), and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G  proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r?1 r ? 1 every vertex of G  becomes activated if at least t(v) t ( v ) of its neighbors are already active by round r?1 r ? 1 . It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G  is hard to approximate to a factor better than O(2log1??|V|) O ( 2 log 1 ? ? | V | ) . In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.
target set selection monotone irreversible dynamic monopolies (dynamo)