1
$\begingroup$

Let $G$ be an undirected graph, seen as a network of 1 Ohm resistors.

As explained by this article (or stated on Wikipedia), the effective resistance between any two vertices can be obtained by taking the pseudo-inverse of the Laplacian matrix $L$ of $G$.

Are there any efficient ways to compute this? Say I am only interested about the effective resistance between a given pair of vertices, in a large graph. I would be interested in the computational complexity of computing that resistance, or any approximation strategy, any preprocessing (lighter than computing the whole matrix) that would make these queries more efficient.

In other words, I am looking for literature about the problem with a computational perspective.

$\endgroup$
  • 1
    $\begingroup$ Matrix operations are efficient. If you want the exact value, it is likely you cannot do any better than inverting the Laplacian. If you are after estimates, it's a different ball game. $\endgroup$ – Yuval Filmus Jun 21 '17 at 15:52
  • $\begingroup$ What kind of objectives in terms of complexity are you looking for? Implemented naively with SVD decomposition, computing the pseudo-inverse of your matrix is $O(|V|^3)$. $\endgroup$ – md5 Jun 21 '17 at 16:00
  • $\begingroup$ @md5: Take PageRank as an example: it can be computed algebraically, but that is not how you compute it at web scale. If I see the web as an undirected graph (I admit that is weird), how do I compute the effective resistance between two pages? $\endgroup$ – pintoch Jun 21 '17 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.