1
$\begingroup$

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

I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ 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 $\mathbf{S}$, and I want to calculate $\Pr(e \in MST(\mathbf{S}))$ for every edge $e$.

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

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

In theory, since I know $p_v$ for all $v$, 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.

Thanks!

Improve this question
$\endgroup$
5
  • $\begingroup$ In theory the "multivariate Tutte polynomial" (see e.g. arxiv.org/abs/math/0503607) contains this information, and so it might be studied in the physics literature, but I doubt it has any useful exact solution. $\endgroup$
    – Sam Hopkins
    Commented Dec 8, 2020 at 20:22
  • 1
    $\begingroup$ What is a "minimum spanning tree"? $\endgroup$
    – markvs
    Commented Dec 8, 2020 at 22:10
  • $\begingroup$ A minimum spanning tree of a graph, is a set of edges (a tree to be precise), that spans all vertices in the graph with the minimum sum of edge weights. $\endgroup$
    – SymX
    Commented Dec 10, 2020 at 3:25
  • $\begingroup$ @SymX So is your graph a weighted graph? This is not included in the original post... $\endgroup$
    – Sam OT
    Commented Dec 10, 2020 at 17:57
  • $\begingroup$ Yes, it is a weighted graph. Thanks for pointing it out, I'll update the question. $\endgroup$
    – SymX
    Commented Dec 12, 2020 at 16:16

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .