  Diffusion on complex networks is often modeled as a stochastic process. Yet,
recent work on strategic diffusion emphasizes the decision power of agents and
treats diffusion as a strategic problem. Here we study the computational
aspects of strategic diffusion, i.e., finding the optimal sequence of nodes to
activate a network in the minimum time. We prove that finding an optimal
solution to this 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.
