21. Minimum Spanning Trees

Exercises

21.1-1

Available in the latest revision of the IM.

21.1-2

Available in the latest revision of the IM.

21.1-3

Available in the latest revision of the IM.

21.1-4

Available in the latest revision of the IM.

21.1-5

Available in the latest revision of the IM.

21.1-6

Available in the latest revision of the IM.

21.1-7

Available in the latest revision of the IM.

21.1-8

Let $G = (V, E)$ be a connected, undirected graph with $n$ vertices. Let $T$ and $T'$ be two minimum spanning trees (MSTs) of $G$. For any real number $w$, let $E_{\le w}$ be the set of all edges in $G$ that have a weight less than or equal to $w$. Let $G_{\le w} = (V, E_{\le w})$ be the subgraph of $G$ containing all vertices of $G$ but only the edges in $E_{\le w}$. Let $c(w)$ be the number of connected components in the subgraph $G_{\le w}$.

Consider the edges of $T$ that have a weight of $w$ or less. Let's call this set $T_{\le w}$. Because $T$ is an MST, $T_{\le w}$ must form a maximal cycle-free subgraph (a spanning forest) of $G_{\le w}$.

Why is it maximal? If it were not maximal, there would exist some edge $e \in E_{\le w}$ that we could add to $T_{\le w}$ without creating a cycle. Since $T$ is a spanning tree of the entire graph $G$, adding $e$ to $T$ must create exactly one cycle, $C$. As in the proof of Theorem 21.1 and Exercise 21.1-6,, we can conclude that every other edge in $C$ must have a weight $\le w(e) \le w$ (the well-known cycle property of MSTs). This means the entire cycle $C$ is contained within $G_{\le w}$, which contradicts the assumption that adding $e$ to $T_{\le w}$ wouldn't create a cycle.

Any spanning forest of a graph with $n$ vertices and $c$ connected components has exactly $n-c$ edges. Thus, the number of edges in both $T$ and $T'$ with weight $\le w$ is exactly $n - c(w)$. Because the number of components $c(w)$ depends only on the original graph $G$ and the threshold $w$ (and not on the specific spanning tree chosen), both $T$ and $T'$ will always have the exact same number of edges with weight $\le w$. Since this holds true for any arbitrary weight $w$, the distribution of edge weights must be identical in both trees. Consequently, their sorted lists of edge weights, $L$, must be the same.

21.1-9

Available in the latest revision of the IM.

21.1-10

Available in the latest revision of the IM.

★ 21.1-11 🌟

Introduces an algorithm for incrementally updating an MST when an "external" edge weight decreases.

The most efficient way to solve this is by using the cycle property of minimum spanning trees (see Exercise 21.1-8). When you add any new edge to an existing spanning tree, it creates exactly one simple cycle. The cycle property states that the heaviest edge on any cycle cannot belong to the minimum spanning tree. Let the edge whose weight decreased be $e = (u, v)$. The step-by-step algorithm is as follows:

1. Add the edge: Temporarily add the updated edge $e$ to your existing minimum spanning tree $T$. The graph $T \cup \{{e}\}$ now contains exactly one cycle, $C$.

2. Find the cycle: Run a DFS on the tree $T$ starting from vertex $u$ to find the path to vertex $v$. This path, along with edge $e$, forms the cycle $C$.

3. Find the heaviest edge: Traverse the edges of the cycle $C$ and identify the edge $e_{max}$ that has the maximum weight. Update $T$:

   1. If $w(e) < w(e_{max})$, then replace $e_{max}$ with $e$ in $T$.

   2. Otherwise, keep the original tree $T$.

Because $T$ is a tree with $\vert{}V\vert{}$ vertices, it has exactly $\vert{}V\vert{} - 1$ edges. Running a DFS to find a path in a tree takes $O(V)$ time. Finding the maximum weight edge on that path also takes $O(V)$ time. Therefore, the entire algorithm runs in $O(V)$ time, which is much faster than recalculating the MST from scratch.

21.2-1

Available in the latest revision of the IM.

The solution in the IM builds upon the property proven in Exercise 21.1-8.

21.2-2

Available in the latest revision of the IM.

21.2-3

Available in the latest revision of the IM.

21.2-4

Available in the latest revision of the IM.

21.2-5

Available in the latest revision of the IM.

21.2-6

Available in the latest revision of the IM.

★ 21.2-7

Available in the latest revision of the IM.

The analysis of Prim's algorithm in the IM is wrong. Because $\log V$ grows significantly slower than $\sqrt{V}$, the IM's complex bucket-based priority queue is actually a downgrade from a standard Fibonacci heap.

Furthermore, the abuse of Big-O notation in the final sentence is mathematically glaring. By stating that Prim's beats Kruskal's when $\vert{}E\vert{} = O(V \sqrt{V})$ is a classic trap of treating Big-O as an exact tight bound rather than an upper bound. If $\vert{}E\vert{} =O(V) = O(V \sqrt{V})$ then the conclusion is obviously false.

★ 21.2-8

Introduces an algorithm for incrementally updating an MST upon adding a new vertex and incident edges to graph whose MST is known.

Available in the latest revision of the IM.

Problems

21-1 Second-best minimum spanning tree

Available in the latest revision of the IM.

21-2 Minimum spanning tree in sparse graphs

a.

By Exercise 21.1-1, we know that the edges added to $T$ are safe. Furthermore, the correctness of the Prim's algorithm ensures that $A$ is an MST of $G'$. The edges in $T$ and $A_\text{orig}=\{(x, y).\text{orig′} : (x, y) ∈ A\}$ are disjoint by construction.

We claim that their union $T'$ is an MST of $G$. Suppose there exists some other spanning tree $T''$ for $G$ such that $w(T'')<w(T')$. Because the edges in $T$ are safe, we can assume $T''$ contains all the edges in $T$. If we take $T''$ and contract all the edges belonging to $T$ (just like the algorithm does to create $G'$), the remaining edges of $T''$ must form a spanning tree for $G'$. Let's call this contracted remainder $A'$. The total weight of the hypothetical better tree is $w(T'') = w(T) + w(A')$. We assumed this is less than $w(T') = w(T) + w(A)$. Subtracting $w(T)$ from both sides leaves us with $w(A')<w(A)$. But this is impossible!

Notice that $T'$ is a tree, since vertices of $G'$ represent sets of connected vertices of $G$ via $T$ and $A$ connects these hyper-vertices.

b.

This follows from the way how MST-Reduce works. Each unmarked vertex $u$ of $G$ is placed into the same vertex set where $v$ belongs for a selected minimum-weight edge $(u,v)$. Therefore, every hyper-vertex of $G'$ represents a vertex set of size at least 2. Furthermore, all such sets of vertices are disjoint.

c.

Here is the $O(E)$ implementation that augments the base variant:

1

Component Labeling (Replacing Disjoint Sets)

Instead of maintaining a disjoint-set data structure, we can select all the safe edges first and then use a simple graph traversal to identify the hyper-vertices.

1. Select Edges: Iterate through the original vertices $V$. For each unmarked vertex $u$, scan its adjacency list to find the minimum-weight incident edge $(u,v)$. Add this edge to a list $T$ and mark both $u$ and $v$. Since we only scan the adjacency list of each vertex once to find its minimum edge, this entire process takes $O(E)$ time.

2. Find Components ($O(V)$ time): Create a temporary graph using the original vertices $V$ and only the edges in $T$. Run a standard BFS or DFS on this graph to find its connected components.

3. Assign IDs ($O(V)$ time): During the traversal, assign a unique integer ID (from 1 to $k$, where $k \le \vert{}V\vert{}/2$ by part (b)) to each connected component. Store this in an array comp[x] = ID for every original vertex $x$. This array perfectly replaces the FIND-SET(x) operation and provides $O(1)$ lookups.

2

Resolving Parallel Edges

Now we need to map the original edges to the new hyper-vertices and filter out duplicate (parallel) edges, keeping only the lightest ones.

1. Map Edges ($O(E)$ time): Iterate through all original edges $(x, y) \in G.E$. Look up their new endpoints: u = comp[x] and v = comp[y]. If $u \neq v$, we have a valid edge for $G'$. Store it in a flat array as a tuple: $( \min(u, v), \max(u, v), (x,y))$. Notice that we also store the original edge.

2. Radix Sort ($O(E)$ time): We need to group edges that connect the same pair of hyper-vertices. Because the hyper-vertex IDs are integers bounded by $\vert{}V\vert{}$, we can sort the list of tuples using Radix Sort (specifically, two passes of Counting Sort: first on the $\max(u, v)$ coordinate, then on the $\min(u, v)$ coordinate). Radix Sort takes $O(E + V)$ time, which simplifies to $O(E)$ since $|E| \ge |V| - 1$ in a connected graph.

3. Filter Duplicates ($O(E)$ time): Because the list is now sorted lexicographically by endpoint pairs, any duplicate edges between the same two hyper-vertices will be adjacent in the array. Do a single linear scan through the sorted array. For each block of identical endpoint pairs, select the one with the minimum weight, add it to $G'.E$, and discard the rest.

3

Finalizing $G'$

Now that $G'.E$ contains the exact, deduplicated set of edges for the contracted graph, simply iterate over $G'.E$ one last time to populate the adjacency lists for $G'$.

d.

Observe that $|G'.V| \le |G.V|/2$ by part (b) and $|G'.E| \le |G.E|$. Each phase demands $O(E)$ time by part (c), which gives $O(kE)$ total time.

e.

By part (b), each phase reduces the number of vertices by at least half. After $k$ phases, the contracted graph $G'$ has $\vert{}V'\vert{} \le \frac{V}{2^k}$ vertices. The number of edges remains bounded by $E$. Combining these, the total asymptotic running time is

$$T(k) = O\left(kE + E + \frac{V}{2^k} \lg V\right) = O\left(kE + \frac{V}{2^k} \lg V\right).$$

If we set $k = \lg \lg V$, then $T(k)=O(E \lg \lg V + V)=O(E \lg \lg V).$ Because we are working with a single connected component, we know $E \ge V - 1$, which justifies the last step.

This hybrid algorithm is specifically designed for sparse graphs (where $E \approx V$), which is where standard Prim's algorithm gets bottlenecked by its $O(V \lg V)$ term. Our running time function $T(k)$ represents a classic trade-off:

• As $k$ increases, the $kE$ term grows, but the $\frac{V}{2^k} \lg V$ term shrinks.

• As $k$ decreases, the $kE$ term shrinks, but the $\frac{V}{2^k} \lg V$ term grows.

To find the minimum asymptotic running time, we must balance these two competing terms so that neither dominates and balloons the overall complexity.

• What if $k$ is smaller? If we pick a smaller $k$, say $k = \lg \lg V - \omega(1)$ (meaning $k$ is asymptotically smaller), the second term becomes $O(V \cdot 2^{\omega(1)})$, which easily overtakes $E \lg \lg V$ for sparse graphs, worsening the time complexity.

• What if $k$ is larger? If we pick a larger $k$, say $k = \lg \lg V + \omega(1)$, the first term becomes $O(E \lg \lg V + E \cdot \omega(1))$, which exceeds our $O(E \lg \lg V)$ bound.

Therefore, setting $k = \lg \lg V$ is the precise "sweet spot" where the cost of contracting vertices exactly neutralizes the expensive priority-queue operations of Prim's algorithm, yielding the absolute lowest upper bound.

f.

Let's set up the inequality $E \lg \lg V < E + V \lg V$. Notice that the $E \lg \lg V$ term on the left will always be asymptotically larger than the standalone $E$ term on the right. Therefore, for the left side to win, the $V \lg V$ term must be the dominant force on the right side, and it must be larger than $E \lg \lg V$. Thus,

$$E \lg \lg V < V \lg V \implies \vert{}E\vert{} = o\left(\frac{\vert{}V\vert{} \lg \vert{}V\vert{}}{\lg \lg \vert{}V\vert{}}\right).$$

21-3 Alternative minimum-spanning-tree algorithms

Available in the latest revision of the IM.

21-4 Bottleneck spanning tree

a.

Suppose $T$ is an MST, whose heaviest edge is $e_{\max}$, but not a bottleneck spanning tree. This means there exists some other spanning tree, let's call it $T_B$ (the actual bottleneck tree), whose maximum edge weight is strictly less than $w(e_{\max})$. If we remove $e_{\max}$ from $T$, it splits it into two disconnected components, creating a cut $(V_1, V_2)$. Because $T_B$ is a valid spanning tree of the whole graph $G$, it must connect $V_1$ and $V_2$. Therefore, $T_B$ must contain at least one edge $e$ that crosses this exact cut. Since $e \in T_B$, its weight can be no larger than the maximum edge in $T_B$. From our initial assumption, we know the maximum edge of $T_B$ is strictly less than $w(e_{\max})$. Now we can safely construct $T' = (T - \{e_{\max}\}) \cup \{e\}$. Because $e$ crosses the cut created by removing $e_{\max}$, it perfectly reconnects the two components. $T'$ is a valid spanning tree with$w(T') = w(T) - w(e_{\max}) + w(e) < w(T)$. This contradicts the fact that $T$ is a minimum spanning tree.

Thus, a minimum spanning tree is a bottleneck spanning tree.

b.

If a bottleneck spanning tree has a value of at most $b$, it means there is some way to connect all the vertices in the graph using only edges that have a weight of $b$ or less. If we simply throw away all edges heavier than $b$, we just need to check if the remaining graph is still connected. This can be done by counting the number of vertices visited via BFS or DFS. We can solve this task in $O(V + E)$ linear time.

c.

Let $G=(V,E)$ be a connected, undirected graph as input to our algorithm. A graph is only connected if $\vert{}V\vert{} \le \vert{}E\vert{} + 1$, so $|E|=\Omega(V)$.

1

Find the Median Weight

Using a linear-time selection algorithm, find the median weight $m$ of all the edges currently in $E$.

2

Partition the Edges

Divide the edges into three sets based on this median. For example, $E_{<m}$ are edges lighter than $m$.

3

Test

Using part (b) as a subroutine, check if the graph is connected using only the edges in $E_{<m} \cup E_{=m}$. There are two possible outcomes:

• Test is negative: This means it is impossible to span the graph using edges of weight $m$or less. The bottleneck edge must be strictly greater than $m$. Because we have to use heavier edges to connect the graph, all the edges in $E_{<m} \cup E_{=m}$ are "safe" to use without exceeding our eventual bottleneck. Just like in MST-Reduce, find the connected components formed by these edges and contract each component into a single hyper-vertex. Recurse on this newly contracted graph using only the edges in $E_{>m}$.

• Test is positive: This means the bottleneck is $\le m$. We can safely throw away all edges in $E_{>m}$. But we still need to know if the bottleneck is exactly $m$, or if it's strictly less than $m$. Run the test again, but this time only use the edges in $E_{<m}$.

  • If positive: The bottleneck is strictly less than $m$. Throw away $E_{=m}$ as well, and recurse on the original vertices using only $E_{<m}$.

  • If negative: The bottleneck is exactly $m$. Stop and return the corresponding DFS tree.

The time complexity forms the recurrence relation $T(E) = T(E/2) + O(E)$, which evaluates to a strictly linear $O(E)$ total time.