8
$\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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.