11.12 Minimum Bottleneck Spanning Trees

Minimum spanning trees minimize the **total weight** of selected edges.

algorithmsgraphsspanning-trees

11.12 Minimum Bottleneck Spanning Trees

Problem

Minimum spanning trees minimize the total weight of selected edges.

In some applications, however, the largest edge matters more than the total cost.

Consider a communication network.

A spanning tree with total cost:

100

and largest edge:

50

may be less desirable than a spanning tree with total cost:

110

and largest edge:

20

The second network has a smaller worst-case link.

Similar situations arise in:

  • Network bandwidth planning
  • Road construction
  • Pipeline design
  • Emergency infrastructure
  • Clustering applications

This leads to a different optimization objective.

Instead of minimizing:

$$ \sum w(e) $$

we want to minimize:

$$ \max w(e) $$

among all edges selected in the spanning tree.

Such a structure is called a Minimum Bottleneck Spanning Tree (MBST).

Solution

A bottleneck spanning tree minimizes the weight of its heaviest edge.

Suppose a spanning tree contains edges:

2
3
5
7
11

Its bottleneck value is:

$$ 11 $$

because 11 is the largest edge.

Among all possible spanning trees, we seek one with the smallest bottleneck value.

Example

Consider:

      10
A -------- B
|          |
|          |
2          4
|          |
|          |
C -------- D
      3

Possible spanning tree:

(A,B)=10
(A,C)=2
(C,D)=3

Bottleneck:

$$ 10 $$

Alternative spanning tree:

(A,C)=2
(C,D)=3
(D,B)=4

Bottleneck:

$$ 4 $$

The second tree is a better bottleneck spanning tree.

Relationship to MST

An important theorem states:

Every minimum spanning tree is a minimum bottleneck spanning tree.

This is one of the most useful results in spanning tree theory.

It means:

MST ⊆ MBST

Every MST automatically minimizes the largest selected edge.

Therefore:

  • Kruskal's algorithm produces an MBST.
  • Prim's algorithm produces an MBST.
  • Borůvka's algorithm produces an MBST.

No modification is required.

Why Every MST Is an MBST

Suppose an MST has largest edge:

$$ b $$

Assume another spanning tree exists with bottleneck:

$$ b' < b $$

This would mean every edge in that tree has weight less than (b).

Then a spanning tree would exist using only edges lighter than (b).

But Kruskal's algorithm only selects an edge of weight (b) when no lighter edge can connect the remaining components.

Therefore such a spanning tree cannot exist.

This contradiction proves the theorem.

Important Observation

The converse is false.

Not every MBST is an MST.

An MBST only minimizes the largest edge.

It does not necessarily minimize total weight.

Example

Graph:

A-B = 1
A-C = 5
B-C = 5
B-D = 5
C-D = 5

Tree 1:

A-B
A-C
B-D

Weight:

$$ 1+5+5=11 $$

Bottleneck:

$$ 5 $$

Tree 2:

A-B
B-C
C-D

Weight:

$$ 1+5+5=11 $$

Bottleneck:

$$ 5 $$

Both are MBSTs.

In larger examples, some MBSTs may have substantially larger total weights than the MST.

Viewing MBST as a Decision Problem

Suppose we ask:

Does there exist a spanning tree whose bottleneck is at most (k)?

This is equivalent to:

  1. Remove every edge with weight greater than (k).
  2. Check whether the remaining graph is connected.

If connected:

Yes

A spanning tree exists using only edges of weight at most (k).

If disconnected:

No

No such spanning tree exists.

This observation leads to efficient algorithms.

Binary Search Approach

Because connectivity changes monotonically as the threshold increases, we can binary search on the bottleneck value.

Procedure

  1. Sort distinct edge weights.
  2. Pick a candidate threshold.
  3. Keep only edges below that threshold.
  4. Check connectivity.
  5. Adjust the search range.

The smallest successful threshold is the bottleneck value.

Example

Weights:

1
3
5
7
10

Check:

≤ 5

Graph disconnected.

Check:

≤ 7

Graph connected.

Result:

7

The bottleneck value is 7.

Connectivity Check

Connectivity testing can use:

  • DFS
  • BFS
  • Union-find

Example:

for edge in edges:

    if edge.weight <= threshold:
        union(u,v)

After processing:

all vertices same component?

If yes, the threshold is sufficient.

Kruskal Perspective

Consider Kruskal's algorithm.

Edges are processed:

1
2
3
4
5
6
...

The last edge added to the MST determines the bottleneck value.

Example:

1
2
3
5

Selected MST edges.

Bottleneck:

$$ 5 $$

This is automatically optimal.

Therefore Kruskal computes both:

  • Minimum total cost
  • Minimum bottleneck value

simultaneously.

Application: Network Design

Suppose edge weights represent:

Latency

rather than monetary cost.

A large latency link can dominate system performance.

An MBST minimizes the worst link.

Example:

Edge Latency
A-B 5 ms
B-C 7 ms
C-D 9 ms
A-D 30 ms

Choosing:

A-D

creates a large bottleneck.

An MBST avoids it whenever possible.

Application: Road Construction

Suppose edge weights represent:

Maximum bridge difficulty

The bottleneck corresponds to the hardest construction project.

Reducing that value may be more important than reducing total cost.

Application: Clustering

Many hierarchical clustering algorithms begin with an MST.

Removing the largest edge creates two clusters.

Removing the two largest edges creates three clusters.

The bottleneck edge often defines natural cluster boundaries.

Complexity

Using MST Algorithms

Kruskal:

$$ O(E \log E) $$

Prim:

$$ O(E \log V) $$

Binary Search Method

Connectivity check:

$$ O(E) $$

Repeated for:

$$ O(\log E) $$

thresholds.

Total:

$$ O(E \log E) $$

Similar to MST construction.

Correctness Intuition

Think of gradually increasing a weight threshold.

Initially:

Only very light edges

Graph disconnected.

As the threshold increases:

More edges appear

Eventually:

Graph becomes connected

The first threshold at which connectivity occurs is precisely the minimum possible bottleneck value.

Any smaller threshold leaves the graph disconnected.

Common Mistakes

Confusing Cost and Bottleneck

Minimum total weight and minimum bottleneck are different objectives.

Assuming Every MBST Is an MST

Only the forward implication is true.

Every MST is an MBST.

Not every MBST is an MST.

Ignoring Connectivity

The bottleneck value is meaningful only for spanning trees.

Disconnected graphs require spanning forests.

Using the Largest Edge in the Graph

The bottleneck concerns the largest edge in the selected spanning tree, not in the original graph.

Theoretical Importance

The theorem:

Every MST is an MBST

provides a strong guarantee for MST algorithms.

Even when an application primarily cares about the worst selected edge, ordinary MST algorithms remain valid solutions.

This is one reason minimum spanning trees appear in such a wide variety of optimization problems.

Recipe

When solving a bottleneck optimization problem:

  1. Determine whether the objective is total cost or maximum edge weight.
  2. Remember that every MST is automatically an MBST.
  3. Use Kruskal or Prim when both objectives are acceptable.
  4. View bottleneck minimization as a connectivity threshold problem.
  5. Use binary search on edge weights when only the bottleneck value is required.
  6. Interpret the bottleneck as the smallest edge limit that still permits connectivity.

Minimum bottleneck spanning trees reveal that spanning tree optimization extends beyond total weight minimization. The next section studies the second-best spanning tree, which answers an important practical question: if the optimal spanning tree becomes unavailable, what is the best alternative?