How is a minimum bottleneck spanning tree different from a minimum spanning tree?

Question

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum spanning tree).

Please give an example where these statements make sense.

Solution 1

Look at the MST example on Wikipedia for reference:

A bottleneck in a spanning tree is a maximum-weight edge in that tree. There may be several bottlenecks (all of the same weight of course) in a spanning tree. In the Wikipedia MST there are two bottlenecks of weight 8.

Now, take a minimum spanning tree of a given graph (there may be several MSTs, all with the same total edge weight of course) and call the maximum edge weight B. In our example B = 8.

Any spanning tree that also has a bottleneck of B = 8 is an MBST. But it may not be an MST (because the total edge weight is bigger than the best possible).

So, take the Wikipedia MST and modify it (add / remove some edges) so that

1. it remains a spanning tree, and
2. it still doesn't use any weight > 8, yet
3. you increase the total edge weight

For example change just the sub-tree "on the left" of the Wikipedia MST (consisting of weights {2, 2, 3}) to {2, 3, 6}, thus increasing total edge weight by 4 without changing the bottleneck of 8. Bingo, you've created an MBST which is not an MST.

Solution 2

Before answering your question, let me define some of the terms that are used here...

1) Spanning Tree : Spanning tree of a given graph is a tree which covers all the vertices in that graph.

2) Minimum spanning tree (MST) : MST of a given graph is a spanning tree whose length is minimum among all the possible spanning trees of that graph. More clearly, for a given graph, list all the possible spanning trees (which can be very large) and pick the one whose sum of edge weights is minimum.

3) Minimum Bottleneck spanning tree (MBST) : MBST of a given graph is a spanning tree whose maximum edge weight is minimum among all the possible spanning trees. More clearly, for a given graph, list all the possible spanning trees and the maximum edge weight for each of the spanning trees. Among these pick the spanning tree whose maximum edge weight is minimum.

Now let us look at the following picture with a four node graph...

Graph-A is the given original graph. If I list all the possible spanning trees for this graph and pick the one whose sum of edge weights is minimum, then I will get the Graph-B. So Graph-B is the Minimum Spanning Tree(MST). Note that its total weight is 1+2+3=6.

Now, if I pick a spanning tree whose maximum edge weight is minimum (i.e MBST), then I may end up picking up either Graph-B (or) Graph-C. Note that both of these spanning trees have maximum edge weight 3, which is minimum among all the possible spanning trees.

From the Graph-B and Graph-C, it is clear that even though the Graph-C is a MBST, it is not MST. Because its total weight is 1+3+3=7, which is greater than the total weight of MST drawn in Graph-B (i.e 6).

So MBST not necessarily be a MST of a given graph. But the MST must be MBST.

Comments

[Nikunj Banka]

you mean editing the edge lengths of {2,2,3} which are on the left and not on the right ?

[dan3]

Of course not, if you CHANGE the weights you have a different graph. Look at the EXISTIG figure, there are edges with weights {2, 2, 3} on the right-side of the bolded MST. Delete those from the bolded tree and replace them with the EXISTING edges labeled 2, 3, and 6. Though I have a feeling you may not understand the basics...

[dan3]

Oh... I mixed up left and right, I was originally looking at another subtree. Fixed.

[celeritas]

@dan3 If the edge weights would have been distinct then MST is the MBST. And vice-versa.

[jobin]

Is that necessarily true? The MBST is not unique still right?

[user2268997]

If the weights are unique then both the MST and MBST would be the same and unique

[Shital Shah]

Great answer. I've put details on algorithm in another SO answer: stackoverflow.com/questions/14297409/…

[G. Bach]

@user2268997 Not true. Take four vertices, connect three of them in a cycle with edges of weights 1,2,3, then connect the fourth vertex to one on the cycle with an edge of weight 4. You have to take the edge of weight 4, and that gives you three MBSTs, only one of which is an MST. Only the MST is always unique in graphs with all-different edge weights. A family of counterexamples are cliques with all-different edge weights plus one additional vertex that connects to the clique with one super-heavy edge; every MBST consists of that edge plus an arbitrary spanning tree of the clique.

[praxmon]

If I consider a bottleneck spanning tree and a minimum spanning tree, then is the MST of a graph a Bottleneck spanning tree? Note that I am talking about a bottleneck spanning tree and not an MBST.