Minimum bottleneck spanning tree

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Minimum bottleneck spanning tree (MBST) is a spanning tree of an undirected graph that minimizes the weight of its heaviest edge. The heaviest edge in a tree is called the bottleneck edge. Among all spanning trees, MBSTs are those whose largest edge is as small as possible. Note that every minimum spanning tree (MST) is an MBST, but an MBST is not necessarily an MST.

Minimum bottleneck spanning arborescence (MBSA) is the directed version. It is a directed spanning tree (an arborescence) rooted at a chosen node that reaches every other node by directed paths, with the bottleneck edge minimized.

Undirected MBST: Camerini’s algorithm
- The algorithm works by splitting edges into two groups: a set of lighter edges and a set of heavier edges.
- If a spanning tree exists using only the lighter edges, compute an MBST there; that MBST is also an MBST of the original graph.
- If not, collapse each connected component formed by the lighter edges into a single “super-vertex.” Then compute an MBST in the graph of these super-vertices using the heavier edges, and combine with the lighter parts.
- Repeat the process, shrinking the graph until only two super-vertices remain, and add the smallest edge between them.
- This procedure runs in linear time in the number of edges (O(E)) for connected graphs.

Directed MBSA: Camerini’s algorithm and Gabow–Tarjan
- For directed graphs, Camerini adapted the idea to find the set of edges that could form a spanning arborescence with the smallest possible bottleneck. It partitions the edge set into two parts and maintains a set that is known not to contain a valid arborescence. Depending on whether a maximum arborescence exists using a union of parts, it expands or shrinks the candidate set. The time complexity is about O(E log E).

- Gabow and Tarjan provide a different approach for MBSA based on a modified version of Dijkstra’s algorithm. This method runs in O(E + V log V) time when using a Fibonacci heap.

- Tarjan and Gabow also produced a refinement with a bound of O(E log* V) for sparse graphs. Their approach introduces a sequence of partitions and a bottleneck value lambda*. After finding lambda*, any spanning arborescence in the graph whose edges all have weight at most lambda* is an MBSA.

Summary
- MBST and MBSA focus on minimizing the heaviest edge in a spanning structure.
- Every MST is an MBST, but MBSTs can exist that are not MSTs.
- There are efficient algorithms for both undirected MBSTs and directed MBSA, including Camerini’s procedures and Gabow–Tarjan’s arborescence methods, with practical time complexities tailored to the graph class and whether it is directed or undirected.