How to sample a lot of independent uniform spanning trees?

2018-07-02 22:44:15

There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only samples one tree at a time.

I have a graph that I want to draw a lot of independent uniform spanning trees from, and I want to know if there is an useful preprocessing kind of step I can do that will make it easy to draw a large number of independent, uniform spanning trees.

Here is one approach: the spanning trees can be put into an efficient bijection with the sandpile group. This suggests that a fast way to generate a lot of random spanning trees by: 1) computing the decomposition of the sandpile group into a product of (hopefully small) Abelian groups 2) Fix a spanning tree T, and draw randomly from this product of abelian groups, and apply them to T. (This is discussed here: https://arxiv.org/pdf/1107.1313.pdf see 6.2)

Has anyone tried this? Are there other methods for