Portal de Periódicos da CAPES

On the approximability of the link building problem

2013; Elsevier BV; Volume: 518; Linguagem: Inglês

10.1016/j.tcs.2013.08.003

1879-2294

Martin Olsen, Anastasios Viglas,

Advanced Graph Theory Research

We consider the LINK BUILDING problem, which involves maximizing the PageRank value of a given target vertex in a directed graph by adding k new links that point to the target (backlinks). We present a theorem describing how the topology of the graph affects the choice of potential new backlinks. Based on this theorem we show that no fully polynomial-time approximation scheme (FPTAS) exists for LINK BUILDING unless P = NP and we also show that LINK BUILDING is W [ 1 ] -hard. Furthermore, we show that this problem is in the class APX by presenting the polynomial time algorithm r -Greedy, which selects new backlinks in a greedy fashion and results in a new PageRank value for the target vertex that is within a constant factor from the best possible. We also consider the naive algorithm π -Naive, where we choose backlinks from vertices with high PageRank values compared to the out-degree and show that this algorithm performs much worse on certain graphs compared to our constant factor approximation. Finally, we provide a lower bound for the approximation ratio of our r -Greedy algorithm.