Treewidth governs the complexity of target set selection Academic Article uri icon


  • In this paper we study the Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos; a problem which gives a nice clean combinatorial formulation for many applications arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that “activates” a pre- specified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i− 1 exceeds its threshold. The activation process is “monotone” in the sense that once a vertex is activated, it remains active for the entire process. Our contribution is as follows: First, we present an algorithm for Target Set Selection running in n O (w) time, for …

publication date

  • February 28, 2011