# Complexity of finding the most likely edge

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?

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.
• 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. Aug 12 '20 at 8:41
• Correction: in time $\widetilde{O}(1/\epsilon^2)$ per edge. Aug 12 '20 at 9:12
• (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. Aug 12 '20 at 9:40