#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!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

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