An exact almost optimal algorithm for target set selection in social networks

The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems 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 prespecified 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.

Unsurprisingly perhaps, Target Set Selection is NPC. More surprising is the fact that both of its maximization and minimization variants turn out to be extremely hard to approximate, even for very restrictive special cases. The only known case for which the problem is known to have some sort of acceptable worst-case solution is the case where the given social network is a tree and the problem becomes polynomial-time solvable. In this paper, we attempt at extending this sparse landscape of tractable instances by considering the treewidth parameter of graphs. This parameter roughly measures the degree of tree-likeness of a given graph, e.g. the treewidth of a tree is 1, and has previously been used to tackle many classical NPhard problems in the literature.

Our contribution is twofold: First, we present an algorithm for Target Set Selection running in n^O(w) time, for graphs with n vertices and treewidth bounded by w. The algorithm utilizes various combinatorial properties of the problem; drifting somewhat from standard dynamic-programming algorithms for small treewidth graphs. Also, it can be adopted to much more general settings, including the case of directed graphs, weighted edges, and weighted vertices. On the other hand, we also show that it is highly unlikely to find an n^O(√w) time algorithm for Target Set Selection, as this would imply a sub-exponential algorithm for all problems in SNPclass. Together with our upper bound result, this shows that the treewidth parameter determines the complexity of Target Set Selection to a large extent, and should be taken into consideration when tackling this problem in any scenario.