1
$\begingroup$

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.)

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

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zachary Hunter Feb 25 at 20:17
  • $\begingroup$ Nice answer, upvoted. Can you edit the question to add a reference that describes Wilson's Algorithm and proves its uniform randomness? $\endgroup$ – Apass.Jack Feb 26 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.