Borůvka cleanup in linear time?

Question

Given boruvka's algorithm:

MST T <- empty tree
Begin with each vertex v 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

In each phase I'd like to reduce the graph's size, by saying that after each phase - there is actually no need to remember edges that are within each component (because some were inserted to the MST T already and others are not needed). So instead of each component I'd like to put only a single vertex. The only problem comes when I try to construct my edges - an edge between two new vertices (which were two components before) is the one with the smallest weight among all the edges between a vertex in the first component and a vertex in the second. I wanted to implement this in linear time, but I don't see how I can reduce the edges as well, all in linear time?

Answer 1

This depends on what you mean by linear time. If you want $O(n)$, then you're out of luck, there's too many edges to consider in the worst case.

If you mean $O(n+m)$, then it is possible, and it is reasonable to consider this as linear time, as the input needs to represent the edges as well as the vertices, which takes at least $O(n+m)$ symbols.

After each round of selecting which new edges to add, we keep track of which pairs of components are being merged, then we look at these in order (any order is fine) and look at all edges from the new component to each other new component, and record the smallest we have seen. (Note that this is symmetric, so we when we find the smallest edge from new component $A$ to new component $B$, it is also the smallest from $B$ to $A$, so we only need to consider edges going to new components later in the ordering, but this doesn't affect the complexity). To achieve this we can simply look at all edges in order and update the appropriate information.