# #StackBounty: #ds.algorithms #graph-theory #pr.probability Complexity of finding the most likely edge

### Bounty: 50

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?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.