15
$\begingroup$

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

Improve this question
$\endgroup$
4
  • $\begingroup$ It would be nice to be awared of such algorithm , but it won't solve this current problem $\endgroup$
    – itamar
    Commented May 15, 2013 at 18:58
  • 2
    $\begingroup$ The graph $G$ will have a unique minimum spanning tree if and only if (1) for any partition of $V(G)$ into two subsets, the minimum weight edge with one endpoint in each subset is unique, and (2) the maximum-weight edge in any cycle of $G$ is unique. $\endgroup$
    – Juho
    Commented May 15, 2013 at 19:03
  • $\begingroup$ Do these question one and two already answer your question? $\endgroup$
    – Juho
    Commented May 15, 2013 at 19:09
  • $\begingroup$ See problem 23-1 in CLRS for how to find the second best MST in $O(n^2)$. $\endgroup$
    – Kaveh
    Commented May 22, 2013 at 3:25

4 Answers 4

Reset to default
7
$\begingroup$

Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs.

My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing one edge with another that you know will reconnect the tree).

For the weighted case they give a running time to list all minimum spanning trees of $O(N\cdot|V|)$ where $N$ is the number of such spanning trees. It enumerates them in order of increasing weight, and my current (cursory) understanding suggests that it's perfectly feasible to terminate the algorithm after it has generated a given number of trees (as it just starts with the MST and produces them sequentially).

Improve this answer
$\endgroup$
7
  • $\begingroup$ In this situation here, we would like to abort the algorithm early once we know that there are more than $k$ solutions. Does the algorithm allow for that? $\endgroup$
    – Raphael
    Commented May 17, 2013 at 6:56
  • 1
    $\begingroup$ @Raphael, I haven't had time to really get to grips with it (yay assignment marking), but from my rough understanding, it should be possible - it starts with some MST, then generates others one by one from it. $\endgroup$
    – Luke Mathieson
    Commented May 17, 2013 at 8:04
  • 1
    $\begingroup$ @SaeedAmiri: "The number of such spanning trees" means "the number of minimum spanning trees", not "the number of spanning trees". If all $n^{n-2}$ spanning trees are minimum spanning trees, then the input graph is complete and all edges have equal weight. $\endgroup$
    – JeffE
    Commented May 17, 2013 at 15:19
  • 1
    $\begingroup$ The paper considers both weighted and unweighted graphs, so you're both right ;). I also think that the algorithm allows the possibility of stopping after you've generated the number of trees you want, so for OP this takes it down to $O(|V|)$. Again, I need some free time to have a better look. $\endgroup$
    – Luke Mathieson
    Commented May 17, 2013 at 21:44
  • 1
    $\begingroup$ After a quick read, the weighted algorithm generates the trees in increasing weight order (starting from an MST obviously). So it should would for the OP's purposes. $\endgroup$
    – Luke Mathieson
    Commented May 17, 2013 at 21:53
2
$\begingroup$

One can show that Kruskal's algorithm can find every minimal spanning tree; see here.

Therefore, you can execute Kruskal and whenever you have multiple edges to choose from, branch. Once you have branched $k$ times, you know that there are at least $k$ different minimal spanning trees. Unfortunately, multiple branches may result in the same tree by adding edges of same weight in different orders, so this does not help much without further work/insight.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ No. If you have to choose between $k$ edges in one step, it might be that those $k$ edges are in all spanning trees. Take for example just a $K_{1,5}$ star with all edges of weight 1. First step, need to choose among the 5 edges, etc. But there is obviously only one spanning tree. Perhaps counting the number of edges with the same weight to an edge included in the spanning tree which are left out helps? Interesting question... $\endgroup$
    – vonbrand
    Commented May 15, 2013 at 20:17
  • $\begingroup$ @vonbrand Good point. We can continue on to finish all branches of the calculation, of course, but then the runtime is determined by the number of spanning trees, which may be exponential. $\endgroup$
    – Raphael
    Commented May 16, 2013 at 5:56
1
$\begingroup$

To see if there is more than one MST, consider e.g. Kruskal's algorithm. The only way it could construct different MSTs is by leaving out edges by choosing another one when there are several with the same weight. But those same-weight edges might have been ruled out because they formed a cycle with lighter edges...

So you should run Kruskal's algorithm, and when there are several edges with the same weight to consider, add all of them that can be added without creating cycles. If there is an edge of this weight left over, and it doesn't close a cycle with any of the edges with lower weights (which were added before), there is more than one MST. Checking if there are exactly 2 or 3 or more, etc looks much harder...

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

Modidying Kruskal's algorithm: While ordering the edges, cluster edges with equal weight. Now, at the point where you process the edges in order, each time you reach a new cluster, first check all edges separately and remove from the cluster those that would close a cycle, given what was built before the cluster. Then run all the remaining edges in the cluster now trying to add them to the MST. If any of them closes a cycle, then that was necessarily because of other edges of the same cluster inserted before, meaning that you have more than one MST.

That solution preserves the complexity of Kruskal's algorithm, only it increases the time for each edge processed.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You seem to be claiming that you can process a whole cluster in constant time but I don't see any obvious constant bound on the size of a cluster. Could you give more detail about how that stage is done? $\endgroup$
    – David Richerby
    Commented Sep 20, 2015 at 17:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.