23-1 Second-best minimum spanning tree

Let $G = (V, E)$ be an undirected, connected graph whose weight function is $w: E \rightarrow \mathbb R$, and suppose that $|E| \ge |V|$ and all edge weights are distinct.

We define a second-best minimum spanning tree as follows. Let $\mathcal T$ be the set of all spanning trees of $G$, and let $T'$ be a minimum spanning tree of $G$. Then a second-best minimum spanning tree is a spanning tree $T$ such that $W(T) = \min_{T'' \in \mathcal T - \{T'\}} \{w(T'')\}$.

a. Show that the minimum spanning tree is unique, but that the second-best minimum spanning tree need not be unique.

b. Let $T$ be the minimum spanning tree of $G$. Prove that $G$ contains edges $(u, v) \in T$ and $(x, y) \notin T$ such that $T - \{(u, v)\} \cup \{(x, y)\}$ is a second-best minimum spanning tree of $G$.

c. Let $T$ be a spanning tree of $G$ and, for any two vertices $u, v \in V$, let $max[u, v]$ denote an edge of maximum weight on the unique simple path between $u$ and $v$ in $T$. Describe an $O(V^2)$-time algorithm that, given $T$, computes $max[u, v]$ for all $u, v \in V$.

d. Give an efficient algorithm to compute the second-best minimum spanning tree of $G$.

a. To see that the minimum spanning tree is unique, observe that since the graph is connected and all edge weights are distinct, then there is a unique light edge crossing every cut. By Exercise 23.1-6, the minimum spanning tree is unique.

To see that the second-best minimum spanning tree need not be unique, here is a weighted, undirected graph with a unique minimum spanning tree of weight $7$ and two second-best minimum spanning trees of weight $8$:

b. Since any spanning tree has exactly $|V| - 1$ edges, any second-best minimum spanning tree must have at least one edge that is not in the (best) minimum spanning tree. If a second-best minimum spanning tree has exactly one edge, say $(x, y)$, that is not in the minimum spanning tree, then it has the same set of edges as the minimum spanning tree, except that $(x, y)$ replaces some edge, say $(u, v)$, of the minimum spanning tree. In this case, $T' = T - \{(u, v)\} \cup \{(x, y)\}$, as we wished to show.

Thus, all we need to show is that by replacing two or more edges of the minimum spanning tree, we cannot obtain a second-best minimum spanning tree. Let $T$ be the minimum spanning tree of $G$, and suppose that there exists a second-best minimum spanning tree $T'$ that differs from $T$ by two or more edges. There are at least two edges in $T - T'$, and let $(u, v)$ be the edge in $T - T'$ with minimum weight. If we were to add $(u, v)$ to $T'$, we would get a cycle $c$. This cycle contains some edge $(x, y)$ in $T' - T$ (since otherwise, $T$ would contain a cycle).

We claim that $w(x, y) > w(u, v)$. We prove this claim by contradiction, so let us assume that $w(x, y) < w(u, v)$. (Recall the assumption that edge weights are distinct, so that we do not have to concern ourselves with $w(x, y) = w(u, v)$.) If we add $(x, y)$ to $T$, we get a cycle $c'$, which contains some edge$(u', v')$ in $T - T'$ (since otherwise, $T'$ would contain a cycle). Therefore, the set of edges $T'' = T - \{(u', v')\} \cup \{(x, y)\}$ forms a spanning tree, and we must also have $w(u', v') < w(x, y)$, since otherwise $T''$ would be a spanning tree with weight less than $w(T)$. Thus, $w(u', v') < w(x, y) < w(u, v)$, which contradicts our choice of $(u, v)$ as the edge in $T - T'$ of minimum weight.

Since the edges $(u, v)$ and $(x, y)$ would be on a common cycle $c$ if we were to add $(u, v)$ to $T'$, the set of edges $T' - \{(x, y)\} \cup \{(u, v)\}$ is a spanning tree, and its weight is less than $w(T')$. Moreover, it differs from $T$ (because it differs from $T'$ by only one edge). Thus, we have formed a spanning tree whose weight is less than $w(T')$ but is not $T$. Hence, $T'$ was not a second-best minimum spanning tree.

c. We can fill in $max[u, v]$ for all $u, v \in V$ in $O(V^2)$ time by simply doing a search from each vertex $u$, having restricted the edges visited to those of the spanning tree $T$. It doesn't matter what kind of search we do: breadth-first, depth-first, or any other kind.

We'll give pseudocode for both breadth-first and depth-first approaches. Each approach differs from the pseudocode given in Chapter 22 in that we don't need to compute $d$ or $f$ values, and we'll use the $max$ table itself to record whether a vertex has been visited in a given search. In particular, $max[u, v] = \text{NIL}$ if and only if $u = v$ or we have not yet visited vertex $v$ in a search from vertex $u$. Note also that since we're visiting via edges in a spanning tree of an undirected graph, we are guaranteed that the search from each vertex $u$—whether breadth-first or depth-first—will visit all vertices. There will be no need to "restart" the search as is done in the $\text{DFS}$ procedure of Section 22.3. Our pseudocode assumes that the adjacency list of each vertex consists only of edges in the spanning tree $T$.

Here's the breadth-first search approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
BFS-FILL-MAX(G, T, w)
    let max be a new table with an entry max[u, v] for each u, v  G.V
    for each vertex u  G.V
        for each vertex v  G.V
            max[u, v] = NIL
        Q = Ø
        ENQUEUE(Q, u)
        while Q != Ø
            x = DEQUEUE(Q)
            for each v  G.Adj[x]
                if max[u, v] == NIL and v != u
                    if x == u or w(x, v) > max[u, x]
                        max[u, v] = (x, v)
                    else max[u, v] = max[u, x]
                    ENQUEUE(Q, v)
    return max

Here's the depth-first search approach:

1
2
3
4
5
6
7
DFS-FILL-MAX(G, T, w)
    let max be a new table with an entry max[u, v] for each u, v  G.V
    for each vertex u  G.V
        for each vertex v  G.V
            max[u, v] = NIL
        DFS-FILL-MAX-VISIT(G, u, u, max)
    return max
1
2
3
4
5
6
7
DFS-FILL-MAX-VISIT(G, u, x, max)
    for each vertex v  G.Adj[x]
        if max[u, v] == NIL and v != u
            if x == u or w(x, v) > max[u, x]
                max[u, v] = (x, v)
            else max[u, v] = max[u, x]
            DFS-FILL-MAX-VISIT(G, u, v, max)

For either approach, we are filling in $|V|$ rows of the $max$ table. Since the number of edges in the spanning tree is $|V| - 1$, each row takes $O(V)$ time to fill in. Thus, the total time to fill in the $max$ table is $O(V^2)$.

d. In part (b), we established that we can find a second-best minimum spanning tree by replacing just one edge of the minimum spanning tree $T$ by some edge $(u, v)$ not in $T$. As we know, if we create spanning tree $T'$ by replacing edge $(x, y) \in T$ by edge $(u, v) \ne T$, then $w(T') = w(T) - w(x, y) + w(u, v)$. For a given edge $(u, v)$, the edge $(x, y) \in T$ that minimizes $w(T')$ is the edge of maximum weight on the unique path between $u$ and $v$ in $T$. If we have already computed the $max$ table from part (c) based on $T$, then the identity of this edge is precisely what is stored in $max[u, v]$. All we have to do is determine an edge $(u, v) \ne T$ for which $w(max[u, v]) - w(u, v)$ is minimum.

Thus, our algorithm to find a second-best minimum spanning tree goes as follows:

  1. Compute the minimum spanning tree $T$. Time: $O(E + V\lg V)$, using Prim's algorithm with a Fibonacci-heap implementation of the priority queue. Since $|E| < |V|^2$, this running time is $O(V^2)$.
  2. Given the minimum spanning tree $T$, compute the $max$ table, as in part (c). Time: $O(V^2)$.
  3. Find an edge $(u, v) \ne T$ that minimizes $w(max[u, v]) - w(u, v)$. Time: $O(E)$, which is $O(V^2)$.
  4. Having found an edge $(u, v)$ in step 3, return $T' = T - \{max[u, v]\} \cup \{(u, v)\}$ as a second-best minimum spanning tree.

The total time is $O(V^2)$.