Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
复制标题
DOI：
--
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;Y. Otachi;Toshiki Saitoh;Hisayuki Satoh;Akira Suzuki;Kei Uchizawa;Ryuhei Uehara;Katsuhisa Yamanaka;Xiaoping Zhou
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Y. Otachi;Toshiki Saitoh;Hisayuki Satoh;Akira Suzuki;Kei Uchizawa;Ryuhei Uehara;Katsuhisa Yamanaka;Xiaoping Zhou
考虑一个建模社交网络的无向图，其中顶点表示用户，边在用户之间建立连接。在竞争扩散博弈中，每个参与者选择一个顶点作为种子来传播他/她的观点，然后它沿着图中的边传播。每个参与者的目标是最大化观点所影响的顶点数量。在本文中，我们研究了一个计算问题，问是否存在一个纯纳什均衡的竞争扩散博弈的加权和未加权的图，并提出了几个否定和肯定的结果。我们首先证明了问题是W[1]-困难时，参数的球员的数量，甚至是无权图。我们还证明了这个问题是NP-困难的，即使是正整数权重的串-平行图，甚至是NP-困难的森林与任意整数权重。此外，我们还证明了具有任意权的路森林问题在伪多项式时间内是可解的;如果给定图是无权的，则它在二次时间内是可解的。我们还证明了问题的链，上链，阈值图与任意整数权重是可解的多项式时间。
Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time.