2020-01-21T00:07:43Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001451172018-03-30T07:23:32Z01164:02592:07834:08333
Computational Complexity of Competitive Diffusion on (Un)weighted GraphsComputational Complexity of Competitive Diffusion on (Un)weighted Graphsenghttp://id.nii.ac.jp/1001/00145084/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=145117&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Information Processing Society of JapanTohoku UniversityJapan Advanced Institute of Science and TechnologyKobe UniversityTohoku UniversityTohoku UniversityYamagata UniversityJapan Advanced Institute of Science and TechnologyIwate UniversityTohoku UniversityTakehiro, ItoYota, OtachiToshiki, SaitohHisayuki, SatohAkira, SuzukiKei, UchizawaRyuhei, UeharaKatsuhisa, YamanakaXiao, ZhouConsider an undirected graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each player chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graph. The objective of every player is to maximize the number of infected vertices. In this paper, we investigate a problem of asking whether a pure Nash equilibrium exists in the game on unweighed and weighted graphs. 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. We then show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time. Moreover, we prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.Consider an undirected graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each player chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graph. The objective of every player is to maximize the number of infected vertices. In this paper, we investigate a problem of asking whether a pure Nash equilibrium exists in the game on unweighed and weighted graphs. 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. We then show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time. Moreover, we prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.AN1009593X研究報告アルゴリズム（AL）2015-AL-1548162015-09-212188-85662015-09-11