Title: Computational Aspects of Optimal Strategic Network Diffusion,
Abstract: The diffusion of information has been widely modeled as stochastic diffusion
processes on networks. Alshamsi et al. (2018) proposed a model of strategic
diffusion in networks of related activities. In this work we investigate the
computational aspects of finding the optimal strategy of strategic diffusion.
We prove that finding an optimal solution to the problem is NP-complete in a
general case. To overcome this computational difficulty, we present an
algorithm to compute an optimal solution based on a dynamic programming
technique. We also show that the problem is fixed parameter-tractable when
parametrized by the product of the treewidth and maximum degree. We analyze the
possibility of developing an efficient approximation algorithm and show that
two heuristic algorithms proposed so far cannot have better than a logarithmic
approximation guarantee. Finally, we prove that the problem does not admit
better than a logarithmic approximation, unless P=NP.