Minimum Spanning Trees

Prev: Depth-First Search Next: Shortest Paths

Exercises

1.

Let $G=(V,E)$ be an arbitrary connected graph with weighted edges. (a) Prove that for any cycle in G, the minimum spanning tree of G excludes the maximum-weight edge in that cycle. (b) Prove or disprove: The minimum spanning tree of G includes the minimum-weight edge in every cycle in G.

2.

Throughout this chapter, we assumed that no two edges in the input graph have equal weights, which implies that the minimum spanning tree is unique. In fact, a weaker condition on the edge weights implies MST uniqueness. (a) Describe an edge-weighted graph that has a unique minimum spanning tree, even though two edges have equal weights. (b) Prove that an edge-weighted graph G has a unique minimum spanning tree if and only if the following conditions hold: • For any partition of the vertices of G into two subsets, the minimumweight edge with one endpoint in each subset is unique. • The maximum-weight edge in any cycle of G is unique. (c) Describe and analyze an algorithm to determine whether or not a graph has a unique minimum spanning tree.

3.

Most classical minimum-spanning-tree algorithms use the notions of “safe” and “useless” edges described in the text, but there is an alternate formulation. Let G be a weighted undirected graph, where the edge weights are distinct. We say that an edge e is dangerous if it is the longest edge in some cycle in G, and useful if it does not lie in any cycle in G. (a) Prove that the minimum spanning tree of G contains every useful edge. (b) Prove that the minimum spanning tree of G does not contain any dangerous edge. (c) Describe and analyze an efficient implementation of the following algorithm, first described by Joseph Kruskal in the same 1956 paper where he proposed “Kruskal’s algorithm”. Examine the edges of G in decreasing order; if an edge is dangerous, remove it from G. [Hint: It won’t be as fast as Kruskal’s usual algorithm.]

4.

(a) Describe and analyze an algorithm to compute the maximum-weight spanning tree of a given edge-weighted graph. (b) A feedback edge set of an undirected graph G is a subset F of the edges such that every cycle in G contains at least one edge in F. In other words, removing every edge in F makes the graph G acyclic. Describe and analyze a fast algorithm to compute the minimum-weight feedback edge set of a given edge-weighted graph.

5.

Suppose we are given both an undirected graph G with weighted edges and a minimum spanning tree T of G. (a) Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased. (b) Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is increased. In both cases, the input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree. [Hint: Consider the cases e \in T and e \notin T separately.]

6.

(a) Describe and analyze an algorithm to find the second smallest spanning tree of a given graph G, that is, the spanning tree of G with smallest total weight except for the minimum spanning tree. (b) Describe and analyze an efficient algorithm to compute, given a weighted undirected graph G and an integer k, the k spanning trees of G with smallest weight.

7.

A graph $G=(V,E)$ is dense if $E=\Theta (V^2)$. Describe a modification of Jarník’s minimum-spanning tree algorithm that runs in $O(V^2)$ time (independent of $E$) when the input graph is dense, using only elementary data structures, in particular without using Fibonacci heaps. This variant of Jarník’s algorithm was first described by Edsger Dijkstra in 1958.

8.

Minimum-spanning tree algorithms are often formulated using an operation called edge contraction. To contract the edge uv, we insert a new node, redirect any edge incident to u or v (except uv) to this new node, and then delete u and v. After contraction, there may be multiple parallel edges between the new node and other nodes in the graph; we remove all but the lightest edge between any two nodes. The three classical minimum-spanning tree algorithms described in this chapter can all be expressed cleanly in terms of contraction as follows. All three algorithms start by making a clean copy $G^{\prime }$ of the input graph G and then repeatedly contract safe edges in $G^{\prime }$; the minimum spanning tree consists of the contracted edges. • Borůvka: Mark the lightest edge leaving each vertex, contract all marked edges, and recurse. • Jarník: Repeatedly contract the lightest edge incident to some fixed root vertex. • Kruskal: Repeatedly contract the lightest edge in the graph. (a) Describe an algorithm to execute a single pass of Borůvka’s contraction algorithm in $O(V+E)$ time. The input graph is represented in an adjacency list. (b) Consider an algorithm that first performs k passes of Borůvka’s contraction algorithm, and then runs Jarník’s algorithm (with a Fibonacci heap) on the resulting contracted graph. i. What is the running time of this hybrid algorithm, as a function of V, E, and k? ii. For which value of k is this running time minimized? What is the resulting running time? (c) Call a family of graphs nice if it has the following properties: • Contracting an edge of a nice graph yields another nice graph. • Every nice graph with V vertices has only $O(V)edges.Forexample,planargraphs—graphsthatcanbedrawnintheplanewithnocrossingedges—arenice.Contractinganyedgeofaplanargraphleavesasmallerplanargraph,andEuler’sformulaimpliesthateveryplanargraphwithVverticeshasatmost3V-6edges.ProvethatBor\mathring{u}vka’scontractionalgorithmcomputestheminimumspanningtreeofanynicegraphin$O(V)$ time.

9.

Consider a path between two vertices s and t in a undirected weighted graph G. The width of this path is the minimum weight of any edge in the path. The bottleneck distance between s and t is the width of the widest path from s to t. (If there are no paths from s to t, the bottleneck distance is $-\infty$; on the other hand, the bottleneck distance from s to itself is $\infty$.) (a) Prove that the maximum spanning tree of G contains widest paths between every pair of vertices. (b) Describe an algorithm to solve the following problem in $O(V+E)$ time: Given a undirected weighted graph G, two vertices s and t, and a weight W, is the bottleneck distance between s and t at most W ? (c) Suppose B is the bottleneck distance between s and t. i. Prove that deleting any edge with weight less than B does not change the bottleneck distance between s and t. ii. Prove that contracting any edge with weight greater than B does not change the bottleneck distance between s and t. (If contraction creates parallel edges, delete all but the heaviest edge between each pair of nodes.) (d) Describe an algorithm to compute a minimum-bottleneck path between s and t in $O(V+E)$ time. [Hint: Start by finding the median-weight edge in G.]

10.

Borůvka’s algorithm can be reformulated to use a standard disjoint-set data structure to identify safe edges, just like Kruskal’s algorithm, instead of explicitly counting and labeling components of the evolving spanning forest F in each iteration. In this variant, each component of F is represented by an up-tree; each vertex v stores a pointer parent(v) to its parent, or to v itself if v is the root of its up-tree. The subroutine Find(v) returns the root of v’s up-tree, but also applies path compression, reassigning all parent pointers from v to the root to point directly to the root, to speed up future Find operations.7 The subroutine Union combines two up-trees into one by making one of the two root nodes the parent of the other.8 Path compression is a form of memoization! Normally, Union is implemented more carefully to ensure that the root of the larger or older up-tree does not change; however, those details don’t matter here.

Find(v):
if parent(v) = v
return v
else
v̄ ← Find(parent(v))
parent(v) ← v̄
return v̄

Union(u, v):
ū ← Find(u)
v̄ ← Find(v)
either
parent(ū) ← v̄
or
parent(v̄) ← ū

In the modified version of Borůvka’s algorithm, in addition to the parent pointers, the root vertex v̄ of each component of F maintains an edge safe(v̄), which (at the end of FindSafeEdges) is the lightest edge with one endpoint in that component.

FindSafeEdges(V, E):
for each vertex v ∈ V
safe(v) ← Null
found ← False
for each edge uv ∈ E
ū ← Find(u)
v̄ ← Find(v)
if ū != v̄
if safe(ū) = Null or w(uv) < w(safe(ū))
safe(ū) ← uv
if safe(v̄) = Null or w(uv) < w(safe(v̄))
safe(v̄) ← uv
found ← True
return found
AddSafeEdges(V, E, F ):
for each vertex v ∈ V
if safe(v) != Null
x y ← safe(v)
if Find(x) != Find(y)
Union(x, y)
add x y to F

Borůvka(V, E):
F ← ∅
for each vertex v ∈ V
parent(v) ← v
while FindSafeEdges(V, E)
AddSafeEdges(V, E, F)
return F

Prove that each call to FindSafeEdges and AddSafeEdges requires only $O(E)$ time. [Hint: What is the depth of the up-trees when FindSafeEdges ends?] It follows that this variant of Borůvka also runs in $O(E\log V)$ time.

Prev: Depth-First Search Next: Shortest Paths