Solution of Bharathi–Kempe–Salek conjecture for influence maximization on arborescence

详细信息    查看全文

• 作者：Zaixin Lu ; Zhao Zhang ; Weili Wu
• 关键词：Bharathi–Kempe–Salek conjecture ; Influence maximization ; In ; arborescence ; Independent cascade (IC) model ; Linear threshold (LT) model ; \({{\mathcal {N}}}{{\mathcal {P}}}\) ; hard
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：803-808
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

Influence maximization is an important problem in social networks. Bharathi et al. (Competitive influence maximization in social networks, pp 306–311, 2007) conjectured that this problem is \({{\mathcal {N}}}{{\mathcal {P}}}\)-hard on arborescence directed into a root. In this short note, we show that the conjecture is true for the independent cascade (IC) model, which is the most studied model in the literature specifying how each node influences other nodes. Therefore, assuming \({\mathcal {P}}\ne {{\mathcal {N}}}{{\mathcal {P}}}\), there exists no polynomial-time algorithm for the influence maximization problem under the IC model on arborescence directed into a root. On the other hand, Wang et al. (J Comb Optim, doi:10.1007/s10878-016-9991-1, 2016) have shown that there exists polynomial-time algorithm for this problem under the linear threshold (LT) model. Hence, this pair of results is of theoretical interest since this is the first time to give a theoretical difference on computational complexity between the IC and LT models. We believe it may motivate further research for influence maximization on arborescence and other special graphs.