{"ID":2827351,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.16087","arxiv_id":"2512.16087","title":"Instance-Optimality in PageRank Computation","abstract":"We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirectional algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order $n$ whose maximum in- and out-degrees are at most a constant fraction of $n$. In other words, there is no correct algorithm that can be faster than our algorithm on any such graph by more than a polylogarithmic factor. We further extend the instance-optimality to all graphs in which at most a polylogarithmic number of vertices have unbounded degrees. This covers all sparse graphs with $\\tilde{O}(n)$ edges. In addition, we provide a counterexample showing that the bidirectional algorithm is not instance-optimal for graphs whose degrees are mostly equal to $n$. We also consider weighted graphs and multigraphs. We show that the bidirectional algorithm is instance-optimal on \\emph{all} multigraphs, but for weighted simple graphs, we have almost the same limitations as for unweighted simple graphs.","short_abstract":"We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirectional algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order $n$ whose maximum in- and out-degrees ar...","url_abs":"https://arxiv.org/abs/2512.16087","url_pdf":"https://arxiv.org/pdf/2512.16087v5","authors":"[\"Mikkel Thorup\",\"Hanzhi Wang\"]","published":"2025-12-18T02:03:37Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}