Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436394 | Theoretical Computer Science | 2014 | 15 Pages |
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⩾1r⩾1 every vertex of G becomes activated if at least t(v)t(v) of its neighbors are already active by round r−1r−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(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.