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), integer values 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 every vertex of G becomes activated if at least t(v) of its neighbors are already 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.