7
$\begingroup$

In a complete graph with $n$ vertices there are $n^{n-2}$ spanning trees.

I want to get a random sample of size $k$ from the set of all spanning trees.

The most basic and naive idea is to generate all spanning trees and select the required sample. But that's costly.

Are there some other approaches? Possibly, enumerating them without generating?

The ideal way would be to set a one-to-one correspondence between a natural number and a spanning tree.

So, for example I generate a random sample of numbers, say $(7,12,5)$, and then, based on these numbers, I get spanning trees.

Improve this question
$\endgroup$
11
  • $\begingroup$ Do you want just random, or uniformly random among the $n^{n-2}$ trees? $\endgroup$
    – Jukka Kohonen
    Commented Nov 14, 2023 at 12:32
  • $\begingroup$ @JukkaKohonen , can you explain the difference? $\endgroup$
    – Paul R
    Commented Nov 14, 2023 at 14:23
  • 1
    $\begingroup$ Propp and Wilson have a nice Monte Carlo method using coupling from the past to ensure you know when to terminate the iteration: "How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph" www2.stat.duke.edu/~scs/Projects/Trees/Theory/… $\endgroup$
    – Dan Piponi
    Commented Nov 14, 2023 at 23:23
  • 3
    $\begingroup$ Uniform distribution, over a discrete set such as "all spanning trees of this graph", simply means that when you pick one element (one tree), each tree has the same probability of being picked. I have no idea what "normal" might be in this context, and if you don't know that either, I guess we can safely ignore that suggestion. $\endgroup$
    – Jukka Kohonen
    Commented Nov 15, 2023 at 8:29
  • 2
    $\begingroup$ @ManfredWeis: generating (uniformly) random unlabeled trees is a much more difficult problem than this one of generating (uniformly) random labeled trees. $\endgroup$
    – Sam Hopkins
    Commented Nov 15, 2023 at 14:42

4 Answers 4

Reset to default
11
$\begingroup$

One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree on $n$ vertices, so this is an easy way to sample a random spanning tree without generating them all.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Prüfer I understand, but how is the random walk defined? Can the walk go back to already visited vertices? Otherwise I don't understand how it can generate any branching trees. $\endgroup$
    – Jukka Kohonen
    Commented Nov 14, 2023 at 18:38
  • 4
    $\begingroup$ The random walk can return to earlier vertices: At each step, it goes to a uniformly chosen random neighbor of its current vertex. For each vertex $v$ other then the starting vertex, let $e_v$ be the edge that was traveled right BEFORE the first time that the walk reaches $v$. The set of edges $\{ e_v \}$ turns out to be a spanning tree, chosen uniformly at random. See Aldous cs.cmu.edu/~15859n/RelatedWork/AldousRandomTrees.pdf . $\endgroup$
    – David E Speyer
    Commented Nov 14, 2023 at 19:20
  • 1
    $\begingroup$ That said, if you specifically want spanning trees of $K_n$, Prufer codes are probably easier. $\endgroup$
    – David E Speyer
    Commented Nov 14, 2023 at 19:21
  • $\begingroup$ Is there a linear time algorithm for turning a Prüfer sequence into a tree? The usual algorithm, for example in Wikipedia, doesn't seem to be linear. I suspect it just needs a better data structure. $\endgroup$
    – Brendan McKay
    Commented Nov 15, 2023 at 0:41
  • 1
    $\begingroup$ @BrendanMcKay In a very naive computation model, you can't beat $n \log n$ steps because you need $n \log n$ bits of input data to encode all the different trees, and you need to look at all the bits. I imagine you are thinking about some sort of model where you can compare $\log n$ bit integers in $O(1)$ time, but you need to be more careful about specifying your computation model if you want to do something like that. $\endgroup$
    – David E Speyer
    Commented Nov 15, 2023 at 20:23
1
$\begingroup$

There is an algorithm for unranking and ranking spanning trees due to Colbourn, Day and Nel which is described in https://www.sciencedirect.com/science/article/abs/pii/0196677489900163

You can compute the number of spanning trees, say $K$ and then generate a random integer in the range $1$ to $K$, say $\ell$ and apply the unranking algorithm to get the $\ell$’th spanning tree.

Improve this answer
$\endgroup$
0
$\begingroup$

A pragmatic solution would be to randomly shuffle the set of edges and assgning them their index in that random sequence as their weight and finally calculate the Minimum-weight Spanning Tree of the thus weighted edge-set with any of the standard algorithms for Minimum-weight Spanning Trees.
Repeat $k$ times to get a random sample of the desired cardinality from the set of spanning trees.

The randomness of the so generated sample depends of course on the quality of shuffling process.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ It should be noted that this process does not yield an uniform distribution over all spanning trees, even if the graph is $K_n$. See math.stackexchange.com/questions/2109978/… $\endgroup$
    – hdur
    Commented Nov 14, 2023 at 20:43
  • $\begingroup$ @hdur the posed question did not make any restrictions on the desired distribution and without knowing the intended use, resp. constraints, there can't be a single 'best' algorithm. $\endgroup$
    – Manfred Weis
    Commented Nov 15, 2023 at 6:45
0
$\begingroup$

Here is another way to generate a spanning tree in a non-uniform way. I added it as a answer, because the exercise that is non-uniform is interesting enough.

Start with the set of $n$-vertices 1,..,n. Pick a random vertex and remove it. Pick a second vertex and leave it in the set. Connect the two vertices. Then repeat until there is only one vertex left in that set.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .