9
$\begingroup$

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 drawing a lot of independent uniform spanning trees that are worth looking in to?

Edit: After we skimmed the paper I'm a little dismayed about some of the constants that appear in their bounds of efficiency. Our graph G is naturally a ribbon graph, so it's possible to use the rotor router action ( https://arxiv.org/abs/0801.3306 ) instead of the bijection described in the first link. It's not clear to me if this will run any faster... we'll experiment and see.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.