  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.
