Some results on the target set selection problem
In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chens result (Discrete Math. 23:14001415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds ?(v)?2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds ?(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,?). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:16151627, 2009).
target set selection viral marketing viral marketing block-cactus graph chordal graph hamming graph tree block graph social networks diffusion of innovations dynamic monopoly irreversible spread of influence