Latency-Bounded Target Set Selection in Social Networks

We study variants of the Target Set Selection problem, first proposed by Kempe et al. In our scenario one is given a graph G = (V, E), integer values t(v) for each vertex v, 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 every vertex of G becomes activated if at least t(v) of its neighbors are active by round 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 |). 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.