I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger Markov process. Though I am aware of theoretical methods for both of these tasks, I was unable to find even rough estimates to complexity coefficients for any process.

My question is, for graphs with 400 vertices, could anyone hazard a guess as to how much faster it is to create a random spanning trees than to count possible spanning trees?

I believe Wilson's algorithm is fastest to create trees uniformly at random. For methods to count spanning trees, there are a few methods, detailed here. (I should note, for the first method, involving matrix factoring, I'm only worried about the time it takes to factor everything, and not the numbering which comes beforehand, because the numbering can be reused. The reason for this is these processes are occurring on subgraphs of a larger 2800 vertex graph, so we can number once and be done with that.)

  • 1
    $\begingroup$ Have you computed even once the number of spanning tree of planar graphs with ~430 vertices? If you are concerned it might take too much time, I would hazard a guess that it is pretty fast. $\endgroup$ – John L. Dec 28 '18 at 0:53
  • $\begingroup$ It's more to see if one takes the bulk of the computation time. I know I likely have to implement each at least once in a single proposal, which will be implemented multiple times for an MCMC sampling. I currently have an idea for a proposal with computable stationary distribution which has to generate multiple random trees (roughly 10) and counts the trees once. I'm hoping to grasp if this majorly the proposal's overall efficiency. $\endgroup$ – Zachary Hunter Dec 28 '18 at 1:17
  • $\begingroup$ I have not checked if the methods your mentioned might be easy enough to implement. If I were you and if I had not any existing code that counts the spanning trees, I will implement the simple counting method explained by j_random_hacker. Note the number of spanning trees is the number of minimum spanning trees of an undirected graph with all edge-weight 1. $\endgroup$ – John L. Dec 28 '18 at 1:28
  • $\begingroup$ The given algorithm checks if the number of spanning trees is greater than 2. I am aware of Kirchoff's Theorem, where you can compute the number via a determinant, but am fairly certain that is much slower than Wilson's algorithm. Where I'm more curious is for the planar specific algorithms linked above, which have complexities of $O(n^{1.5})$ and $O(n^2)$. $\endgroup$ – Zachary Hunter Dec 28 '18 at 1:33
  • $\begingroup$ I just realized that algorithm by j_random_hacker is indeed irrelevant here since there is only one block of edges. $\endgroup$ – John L. Dec 28 '18 at 1:49

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.