On the complexity of optimizing PageRank

We consider the PageRank Optimization problem in which one seeks to maximize (or minimize) the PageRank of a node in a graph through adding or deleting links from a given subset. The problem can be modeled as a Markov Decision Process and has recently received much attention. We provide provably efficient methods to solve the problem on large graphs for a number of cases of practical importance and we show using perturbation analysis that for a close variation of the problem, the same techniques have exponential worst case complexity.