2014/12/10 by Takehiro Ito, Ito, Takehiro, Yota Otachi +15
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Limits and Structures in Graph Theory #Social and Information Networks (cs.SI) #cs.CC #cs.DS #cs.GT #cs.SI
paper · pdf · doi:10.48550/arxiv.1412.3334
34 pages, 5 figures
arxiv created 2014/12/10 · openalex publication_date 2014/12/10 · arxiv updated 2014/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.