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 Chen’s result (2009) for trees, and the time complexity is much better than the algorithm in Ben‐Zwi et al. (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 (2009).
