Some results on the target set selection problem

Chun Ying Chiang, Liang Hao Huang, Bo Jr Li, Jiaojiao Wu, Hong Gwa Yeh

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

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).

Original languageEnglish
Pages (from-to)702-715
Number of pages14
JournalJournal of Combinatorial Optimization
Volume25
Issue number4
DOIs
StatePublished - May 2013

Keywords

  • Block graph
  • Block-cactus graph
  • Chordal graph
  • Diffusion of innovations
  • Dynamic monopoly
  • Hamming graph
  • Irreversible spread of influence
  • Social networks
  • Target set selection
  • Tree
  • Viral marketing

Fingerprint

Dive into the research topics of 'Some results on the target set selection problem'. Together they form a unique fingerprint.

Cite this