Tighter analysis of modified Borůvka's algorithm

Question

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.

The pseudo-code is:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

We call each iteration of the outer loop a round. In each round, the inner loop cuts the number of components at least in half. Therefore there are at most $O(\log n)$ rounds. In each round, the inner loop looks at each edge at most twice (once from each component). Therefore the running time is at most $O(m \log n)$.

Now suppose after each round, we remove all the edges which only connect vertices within the same component and also remove duplicate edges between components, so that the inner loop only looks at some number of edges m' < m which are the minimum weight edges which connect two previously disconnected components.

How does this optimization affect the running time?

If we somehow knew that in each round, it would cut the number of edges in half, then the running time would be significantly improved: $T(m) = T(m /2) + O(m) = O(m)$.

However, while the optimization will dramatically reduce the number of edges examined, (only 1 edge by the final round, and at most # of components choose 2 in general), it's not clear how/if we can use this fact to tighten the analysis of the run-time.

Answer 1

It is possible to craft test cases for general graphs where your Borůvka's step wouldn't halve the number of edges in each step, even though it halves the number of vertices. An interesting note is that the optimization that you suggest works for planar graphs. This is because for planar graphs $|E| \leq 3*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads to a speed up for the class of minor closed families of graphs.

Reference:

• Masters thesis, Claude Anderson (on page 100 the worst case input for Borůvka's algorithm is described). [link]

• "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320, 2004. [link]