<p>If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time <span class="math-container">$\widetilde{O}(m)$</span>. This is done explicitly in <a href="https://arxiv.org/abs/0803.0929" rel="nofollow noreferrer">this paper</a> by Spielman and Srivastava, Theorem 2.</p>
<p>My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.</p>

CC BY-SA 4.0
2020-08-12T08:37:11.083Z
Do you have to do this once per edge?
Simd
CC BY-SA 4.0
2020-08-12T08:41:44.650Z
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.
smapers
CC BY-SA 4.0
2020-08-12T09:12:36.360Z
Correction: in time $\widetilde{O}(1/\epsilon^2)$ per edge.
smapers
CC BY-SA 4.0
2020-08-12T09:22:52.413Z
That is really a huge improvement. For an exact answer is the OPs complexity optimal?
Simd
CC BY-SA 4.0
2020-08-12T09:40:19.447Z
(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.
smapers
CC BY-SA 4.0
2020-08-12T06:37:21.260Z
2020-08-12T06:37:21.260Z
smapers
<p>Consider a connected, unweighted, undirected graph <span class="math-container">$G$</span>. Let <span class="math-container">$m$</span> be the number of edges and <span class="math-container">$n$</span> be the number of nodes.</p>
<p>Now consider the following random process. First sample a uniformly random spanning tree of <span class="math-container">$G$</span> and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.</p>
<p>There is a probability distribution on edges implied by this process.  <a href="https://math.stackexchange.com/a/3781031/678546">https://math.stackexchange.com/a/3781031/678546</a> points out that if <span class="math-container">$T$</span> is a uniform sampled spanning tree then</p>
<p><span class="math-container">$$P(e \in T) = \mathscr{R}(e_- \leftrightarrow e_+)$$</span></p>
<p>where <span class="math-container">$e = \{e_-, e_+\}$</span> and <span class="math-container">$\mathscr{R}(a \leftrightarrow b)$</span> is the effective resistance between <span class="math-container">$a$</span> and <span class="math-container">$b$</span> when each edge is given resistance <span class="math-container">$1$</span>.</p>
<p>Marcus M goes on to give a complexity of <span class="math-container">$O(mn^3)$</span> for computing the probabilities for every edge.  This is much too slow to run in practice for all but the smallest graphs.</p>
<p>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?</p>

<ds.algorithms><graph-theory><pr.probability>
Complexity of finding the most likely edge
Simd
# Complexity of finding the most likely edge

(Asked by: username_0 on 2020-08-08)

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?

**Tags:** ds.algorithms, graph-theory, pr.probability

---

## 1 answers

### Answer by username_1 on 2020-08-12. Score: 3 | Accepted answer

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](https://arxiv.org/abs/0803.0929) 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.

> **Comments:**
> **username_0**: Do you have to do this once per edge?  
> **username_1**: 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.  
> **username_1**: Correction: in time $\widetilde{O}(1/\epsilon^2)$ per edge.  
> **username_0**: That is really a huge improvement. For an exact answer is the OPs complexity optimal?  
> **username_1**: (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.  

---

