Some results on the target set selection problem

• Published in: Journal of combinatorial optimization 2013-05, Vol.25 (4), p.702-715
• Main Authors: Chiang, Chun-Ying, Huang, Liang-Hao, Li, Bo-Jr, Wu, Jiaojiao, Yeh, Hong-Gwa
• Format: Article
• Language: English
• Subjects: Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Theory of Computation
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-012-9518-3

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 (Discrete Math. 23:1400–1415, 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:1615–1627, 2009 ).