Consider the following divideandconquer algorithm for determ

Consider the following divide-and-conquer algorithm for determining minimum spanning trees. Suppose G is an undirected, connected, weighted graph with distinct edge weights. If G is a single vertex, then the algorithm just returns, outputting nothing. Otherwise, it divides the set of vertices of G into two sets, V₁ and V₂, of nearly equal size. Let e be the minimum-weight edge in G that connects V₁ and V₂. Output e as belonging to the minimum spanning tree. Let G₁ be the subgraph of G induced by V₁ (that is, G₁ consists of the vertices in V₁ plus all the edges of G that connect pairs of vertices in V₁). Similarly, let G₂ be the subgraph of G induced by V₂. The algorithm is then recursively executed on G₁ and G₂. Does this algorithm output exactly the edges of the minimum spanning tree of G? If the algorithm is correct, prove its correctness. If not, give a counterexample to prove that the algorithm is incorrect.

Solution

The claim is false. Consider the following counterexample. Let G and G’ be undirected graphs with V = {a,b,c} and E = {(a,b),(b,c),(c,a)}. Define the weight function w by w(a,b) = 6,w(b,c) = 4, w(c, a) = 3 and consider the shortest path between nodes a and b. The edge (a, b) constitutes the shortest path in graph G, whereas the edge set {(a, c), (c, b)} constitutes the shortest path in graph G’.

The claim is true. Consider an execution of Prim’s algorithm on G that led to the tree T. To see that the same execution sequence is valid on the graph G’ we use the monotonicity of the ()2(·)2 function and proceed by induction. With the same starting node s in both cases, squaring the edge weights does not change the minimum weight edge and hence the first edge added to the partial tree is the same for both graphs G and GO. Now assume that the same set of edges have been added to the partial tree up to stage k on both graphs. So the edges to consider at stage k + 1, i.e. the edges that do not form a cycle, are exactly the same for both graphs. Among these candidate edges, squaring the edge weights does not change the minimum weight edge so that addition of the same edge is valid for both G and GO. Hence, the partial trees are the same for both graphs after stage k + 1 and the proof is complete by mathematical induction.