# Complexity of finding the leading eigenvector of a graph Laplacian

Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?

Are there any families of Laplacians for which it takes almost linear time?

• does linear time mean $O(n^2)$ or $O(m)$ ($m$ being the number of edges in the graph) ? – Suresh Venkat Oct 30 '11 at 21:45
• I think $O(m)$ is more appropriate since -to the best of my understanding- $O(n^2)$ is the cost of a principal eigenvector for a "generic" $n\times n$ matrix. If we assumed O(n^2) to be linear I think that it would imply the answer "all Laplacians" to the second question. I am not sure though. – Dimitris Oct 30 '11 at 22:57
• Are you interested in exact or approximate solutions? Btw, what is the reference for the O(n^2) solution you mention? For approximate solutions, there are the Lanczos/power methods that run in near-linear time (I think). – Alex Andoni Nov 4 '11 at 19:27
• Either exact or approximate within $\epsilon$ is fine. I think that the power method is $O(n^2)$ modulo the approximation error: ${\bf L}^i{\bf x}$ costs O(n^2) per iteration, and the number of iterations to approach the optimal solution within $\epsilon$ is a function of the two largest eigenvalues. I might be missing something. Do you have a references for the near-linear time? – Dimitris Nov 4 '11 at 23:28
• A standard reference seems to be: "J. Kuczynski and H. Wozniakowski. Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications, 13:1094–1122, 1992." It obtains $1+\epsilon$ approximation in $O(1/\epsilon\cdot m\cdot \log n)$ time (essentially, note that an iteration of the power method runs in $O(m)$ time). The approximation means to find a vector $x$ s.t. $x^tLx\ge (1-\epsilon)\lambda_1\|x\|^2$. If the eigenvalues drop sufficiently rapidly, then one can get even better estimates. – Alex Andoni Nov 5 '11 at 18:32