Provide a formal proof of the correctness of the algorithm b

Provide a formal proof of the correctness of the algorithm by Boruvka/Solllin for finding a MST

Solution

The solution starts as follows. Lets first see whats the Boruvka Algorithm:

Borvka’s algorithm

Like Kruskal’s algorithm, Borvka’s partitions the vertices into partial trees and merges them incrementally. However, unlike Kruskal’s, which merges two compo- 15 nents in a step, in a single step of Borvka’s algorithm every component is involved in a merger.

Like DJP (Dijkstra-Jarník-Prim), Borvka’s grows the intermediate result by taking the lightest edge coming out of a component, but unlike DJP, which only tracks one component, Borvka’s does so for many. Of course the cost of taking multiple edges in a step is that the steps are longer and more complex.

One iteration of Borvka’s algorithm

At the start iteration i, we have a graph Gi , with G0 = G. During one iteration, each vertex selects the lightest edge incident to it and contracts that edge. At the end of the iteration, we have some contraction Gi+1 of Gi , and the set F of contracted edges. In the implementation given in Algorithm 3, we need to store fields “minEdge” and “minEdgeWeight” for each vertex. Algorithm 3 Borvka-step Require: Input: Gi = (Vi , Ei) Ensure: Output: a forest F of MST edges and a contracted graph G0 F for all {u, v} Ei do if w({u, v}) < u.minEdgeWeight then u.minEdgeWeight w({u, v}) u.minEdge {u, v} end if if w({u, v}) < v.minEdgeWeight then v.minEdgeWeight w({u, v}) v.minEdge {u, v} end if end for for all v V do put v.minEdge in F end for Gi+1 contract (Gi , F) return Gi+1, F Iterating through the edge set and vertex set takes O(m + n) time, and contract is O(m), so Borvka-step takes O(m) time in all. 16 3.2.2 The algorithm Borvka’s algorithm simply performs Borvka phases until the entire graph is contracted into one vertex. It stores a running result T, and appends the contracted edges F to T after every iteration. It is easy to see correctness by noting that taking the lightest edge out of a vertex v 0 in G0 is equivalent to taking the lightest edge out of the cut Sv 0, S¯ v 0, where Sv 0 is the vertex set of Cv 0. And we iterate until G is contracted to a single vertex, so the final T is connected.

Boruvka’s algorithm

1. Initially all edges of G are uncolored and let each vertex of G be a trivial blue tree.

2. Repeat the following coloring step until there is only one blue tree.

3. Coloring step: For every blue tree T, select the minimum-weight uncolored edge incident to T. Color all selected edges blue.

Proof (Correctness of Boruvka’s algorithm). It is easy to see that at the end of Boruvka’s algorithm the blue colored edges form a spanning tree (in each step the distinct edge-weights guarantee to get a blue forest containing all vertices).