I've been running into this problem recently and I've been stuck on it for a while.

I have a set of vertices 𝐺 that form a complete graph. From this I need to sample π‘˜ vertices (which would also form a complete graph), and calculate (or estimate) the probability that each edge (pair of vertices) that was sampled will be part of a minimum spanning tree (MST) in the sampled graph. In other words, I sample a subset of vertices 𝐒, and I want to calculate Pr(π‘’βˆˆπ‘€π‘†π‘‡(𝐒)) for every edge 𝑒.

For each vertex 𝑣, I have a binomial distribution 𝑝𝑣, that determines the probability of the edge being sampled or not.

This gets tricky because the probability of 𝑒 being in an MST doesn't only depend on 𝑒, but also on what are the other edges that also were sampled.

In theory, since I know 𝑝𝑣 for all 𝑣, I can determine the dependency of each edge on other edges, to calculate the probability of an edge being in an MST of the sampled graph. In practice, determine this dependency is too costly to compute for large graphs, so it doesn't scale.

I'm starting to think that this is not something I can calculate exactly in an scalable way, but perhaps there's some trick I can use to come up with an approximation.

I would appreciate any help anyone can give.


  • $\begingroup$ I think the description of the problem could be clearer. If the MST is randomly chosen from all possible MSTs of the complete graph, then by symmetry each edge has probability has $\frac{(|V|-1)}{|E|}$ of being an edge of the MST - but it's not clear whether this is actually the situation you're describing. $\endgroup$ – fblundun Dec 8 '20 at 21:51

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.