Parameterized Complexity of Influence Maximization
摘要
The influence maximization problem studies how to select a set of nodes as initial seeds in a social network to maximize their influence. A dual problem of the influence maximization problem is the target set selection problem that asks for a minimum-cardinality seed set that can influence all users in the social network. In this paper, we consider the decision problem of deciding if we can select at most k seeds to influence at least t users in expectation, which formulates both the influence maximization problem and the target set selection problem. We study the parameterized complexity of this decision problem and consider the two most studied diffusion models: the independent cascade model (IC) and the linear threshold model (LT). We show that the problem is W[1]-hard under both models even if both k and t are given as parameters. For the special case with t being the number of the vertices in the network (which coincides with the target set selection problem), we show that the problem under the IC model is polynomial-time solvable, and the problem under the LT model, known to be NP-hard, is fixed-parameter tractable parameterized by k.