# Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.

We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.

Let's call that determinant t (i.e. there are t possible spanning trees in total).

What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?

Here's the algorithm I'm using currently.

Definitions:

$V_{visited}$ - vertices already traversed

$E_{visited}$ - edges already traversed

$V_C$ - V \ V_visited (i.e. vertices in V but not in $V_{visited}$)

N($V_{visited}$) - the set of all vertices v in $V_C$ such that an edge exists between v and some vertex in $V_{visited}$

Algorithm:

• sample $v_0$ from V randomly
• add $v_0$ to $V_{visited}$
• sample $v_1$ from N($V_{visited}$) randomly
• add ($v_0$, $v_1$) to $E_{visited}$
• sample $v_2$ from N($V_{visited}$) randomly
• add ($v_*$, $v_2$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_2$'s neighbors in $V_{visited}$)

...

• sample $v_{|V| - 1}$ (the second to last vertex in V) randomly
• add ($v_*$, $v_{|V| - 1}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V| - 1}$'s neighbors in $V_{visited}$)
• sample $v_{|V|}$ (the last vertex in V)
• add (v*, $v_{|V|}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V|}$'s neighbors in $V_{visited}$)

Now $V_{visited}$ and $E_{visited}$ represents a random spanning tree of G.

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)

• Take a look at this paper and its references. Perhaps one of these algorithms is practical. – Yuval Filmus Sep 12 '18 at 5:13

## 1 Answer

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $$n^3$$, but in practical usage it often runs much faster, I believe typically $$n log(n)$$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.

At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.

Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)

• There's also the older Andrei Border algorithm. There's some interesting modifications of it which are faster asymptotically, but only for graphs which are unfeasibly large. Practically I do not see any use for it but perhaps it is worth looking into. – Zachary Hunter Feb 25 '19 at 20:17
• Nice answer, upvoted. Can you edit the question to add a reference that describes Wilson's Algorithm and proves its uniform randomness? – John L. Feb 26 '19 at 14:24