5
$\begingroup$

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.

Now consider the following random process. First sample a uniformly random spanning tree of $G$ and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.

There is a probability distribution on edges implied by this process. https://math.stackexchange.com/a/3781031/678546 points out that if $T$ is a uniform sampled spanning tree then

$$P(e \in T) = \mathscr{R}(e_- \leftrightarrow e_+)$$

where $e = \{e_-, e_+\}$ and $\mathscr{R}(a \leftrightarrow b)$ is the effective resistance between $a$ and $b$ when each edge is given resistance $1$.

Marcus M goes on to give a complexity of $O(mn^3)$ for computing the probabilities for every edge. This is much too slow to run in practice for all but the smallest graphs.

If I only want to find an edge with the maximal probability, is there a faster algorithm? How about if I am happy with an approximation?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
+50
$\begingroup$

If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time $\widetilde{O}(m)$. This is done explicitly in this paper by Spielman and Srivastava, Theorem 2.

My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Do you have to do this once per edge? $\endgroup$
    – Simd
    Aug 12, 2020 at 8:37
  • $\begingroup$ No. In $\widetilde{O}(m/\epsilon^2)$ time you can can construct a data structure, which then allows to $\epsilon$-approximate any effective resistance in time $\widetilde{O}(1)$ per edge. $\endgroup$
    – smapers
    Aug 12, 2020 at 8:41
  • 1
    $\begingroup$ Correction: in time $\widetilde{O}(1/\epsilon^2)$ per edge. $\endgroup$
    – smapers
    Aug 12, 2020 at 9:12
  • $\begingroup$ That is really a huge improvement. For an exact answer is the OPs complexity optimal? $\endgroup$
    – Simd
    Aug 12, 2020 at 9:22
  • 1
    $\begingroup$ (i) I clarified in the linked question of the OP that the actual time complexity is matrix multiplication time (so $O(n^{2.373})$ rather than $O(mn^3)$), (ii) my guess would be that this is optimal. $\endgroup$
    – smapers
    Aug 12, 2020 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.