Borůvka's Algorithm

Borůvka's algorithm (also known historically as Sollin's algorithm) is a greedy graph optimization algorithm within computation and algorithms that computes a minimum spanning tree (MST) or minimum spanning forest of an undirected edge-weighted graph G = (V, E, w) in O(E log V) worst-case time. Published in 1926 by Czech mathematician Otakar Borůvka to design the most economical electrical power distribution grid across northern Moravia, it is the oldest documented minimum spanning tree algorithm—predating Jarník/Prim's algorithm (1930/1957) and Kruskal's algorithm (1956) by decades.

Whereas Prim's algorithm grows a single tree sequentially one vertex at a time and Kruskal's algorithm requires a global pre-sorting of all E edges, Borůvka's algorithm operates in synchronous parallel rounds (Borůvka phases). In each round, every currently active connected component simultaneously identifies the minimum-weight edge connecting it to a distinct component, adds all selected edges to the spanning forest, and contracts the resulting components. Because every active component merges with at least one neighbor in each phase, the number of connected components drops by at least a factor of two per round, guaranteeing termination in at most ⌊log₂ V⌋ rounds and making Borůvka's method the foundational building block for GPU-parallel, distributed, planar linear-time, and Karger–Klein–Tarjan randomized linear-time MST solvers.

The Cut Property and Cycle-Free Simultaneous Selection

In an undirected graph G = (V, E, w), the cut property of minimum spanning trees states that for any subset of vertices S ⊂ V (such as an existing connected component of a partial spanning forest), the minimum-weight edge e* = arg min_e∈δ(S) w(e) crossing the cut δ(S) between S and V \ S is guaranteed to belong to every minimum spanning tree of G whenever all edge weights are distinct.

What happens when every component C₁, C₂, …, C_k selects its minimum-weight outgoing edge e(C_i) simultaneously in the same round? If two components C₁ and C₂ both pick the same shared edge between them, that edge is simply added once, merging C₁ and C₂. Could a set of components C₁, C₂, …, C_r (r ≥ 3) form a closed cycle of chosen edges where C₁ picks an edge to C₂, C₂ picks an edge to C₃, …, and C_r picks an edge back to C₁?

Assume edge weights are distinct (or made distinct by lexicographic tie-breaking (w(e), min(u, v), max(u, v))). For each component C_i in the hypothetical cycle to prefer its forward edge e_i = (C_i, C_i+1) over its backward edge e_i−1 = (C_i−1, C_i), the weights must satisfy the strict chain of inequalities:

which implies the contradiction w(e₁) < w(e₁). Therefore, under consistent lexicographic tie-breaking, the set of minimum outgoing edges selected simultaneously by all components in a Borůvka phase is strictly acyclic (a forest of pseudotrees whose only cycles have length 2).

Logarithmic Round Bound and O(E log V) Complexity

Let k_t denote the number of non-isolated connected components at the beginning of round t (with k₀ ≤ V). During round t, each of the k_t components selects one incident edge and merges with at least one other component, so every resulting merged component contains at least two former components:

Thus the algorithm terminates after at most ⌊log₂ V⌋ rounds. Within a single round, scanning all E edges once to update cheapest[find(u)] and cheapest[find(v)] and merging the chosen edges in a disjoint-set data structure (or contracting supervertices via connected-component labeling) takes O(E + V) time, yielding a total worst-case runtime of O(E log V) without sorting the edges or maintaining a complex priority queue.

Strict O(V) Linear Time on Planar and Minor-Closed Graphs

A remarkable property of Borůvka's algorithm Occurs when each round explicitly contracts the merged components into single supervertices, removes self-loops, and retains only the minimum-weight edge among parallel edges between any pair of supervertices. Because edge contractions preserve graph planarity (planar graphs—and more generally any proper minor-closed graph family—are closed under taking graph minors), Euler's polyhedral formula guarantees that a simple planar graph on n_t vertices contains at most 3n_t − 6 edges.

In round t of Borůvka's algorithm with explicit contraction and parallel-edge deduplication (implemented in O(n_t) time via radix bucket sorting of endpoint pairs), the vertex count shrinks geometrically as n_t ≤ V / 2^t, which forces the edge count to shrink geometrically as well: m_t < 3n_t ≤ 3V / 2^t. Summing the work across all rounds yields a convergent geometric series:

Thus Borůvka's algorithm with vertex contraction solves the minimum spanning tree problem on planar graphs in deterministic O(V) linear time.

Role in Chazelle's and Karger–Klein–Tarjan's Optimal MST Algorithms

Every modern sub-logarithmic and linear-time minimum spanning tree algorithm uses Borůvka phases to shrink the number of vertices before invoking heavier machinery:

• Fredman–Tarjan (1987) and Chazelle (2000): Running k rounds of Borůvka's algorithm reduces the number of vertices from V to V / 2^k in O(kE) time, reducing the subsequent Extract-Min overhead in Fibonacci heaps or soft heaps (yielding Chazelle's deterministic O(E α(E, V)) bound).
• Karger–Klein–Tarjan Randomized Linear-Time MST (1995): Interleaves two Borůvka contraction steps (reducing the vertex count by a factor of 4) with random subgraph sampling (including each edge with probability p = 1/2) to filter out "F-heavy" edges via linear-time tree path verification, achieving O(E) expected time on arbitrary graphs.

Because each component's minimum outgoing edge in a Borůvka phase depends only on local incident edges, Borůvka's algorithm is the standard choice for Graphics Processing Units (GPUs), MapReduce/Spark clusters, and shared-memory multi-core systems. On GPUs, each thread block scans adjacency lists in parallel and updates cheapest[c] using hardware 64-bit atomic minimum instructions (atomicMin on packed (weight ≪ 32) | edgeID words), followed by parallel pointer jumping (parent[v] ← parent[parent[v]]) to contract star trees in O(log V) parallel depth.

Why is Borůvka's algorithm sometimes called Sollin's algorithm in operations research literature?

Otakar Borůvka published his original 1926 paper in Czech ("O jistém problému minimálním") in the transactions of the Moravian Natural Science Society, and a brief German summary in 1927. Unaware of Borůvka's work, French mathematician Georges Sollin independently rediscovered the parallel component-contraction method in 1961 (published in 1965), leading several 1960s and 1970s operations research textbooks to call it Sollin's algorithm before historical surveys by Graham and Hell (1985) and Nešetřil, Milková, and Nešetřilová (2001) restored credit to Borůvka.

What goes wrong if edge weights have ties and components break ties inconsistently?

Suppose three components A, B, and C are mutually connected by three edges of equal weight w = 5: e₁ = (A, B), e₂ = (B, C), and e₃ = (C, A). If A breaks its tie in favor of e₁, B breaks its tie in favor of e₂, and C breaks its tie in favor of e₃, all three edges are added simultaneously, creating a 3-cycle {e₁, e₂, e₃} that violates the tree property. Breaking ties by a fixed global total order on edges—such as comparing the tuple (w(e), min(u, v), max(u, v)) or (w(e), edgeIndex)—ensures that one edge in the triangle is strictly largest under the total order and can never be chosen by either of its endpoints.

How does Borůvka's algorithm handle disconnected graphs?

Without any modification to its control flow, Borůvka's algorithm computes a minimum spanning forest on disconnected graphs: in each round, every component that still has at least one edge to a different component inside its own connected subgraph selects its minimum outgoing edge and merges, while components that have already spanned their entire connected subgraph find no outgoing edges and become quiescent.

1. Borůvka, O. (1926). "O jistém problému minimálním (About a certain minimal problem)." Práce Moravské přírodovědecké společnosti, 3(3), 37–58. https://dml.cz/handle/10338.dmlcz/500114
2. Nešetřil, J., Milková, E., & Nešetřilová, H. (2001). "Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history." Discrete Mathematics, 233(1–3), 3–36. https://doi.org/10.1016/S0012-365X(00)00224-700224-7)
3. Graham, R. L., & Hell, P. (1985). "On the history of the minimum spanning tree problem." Annals of the History of Computing, 7(1), 43–57. https://doi.org/10.1109/MAHC.1985.10011
4. Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). "A randomized linear-time algorithm to find minimum spanning trees." Journal of the ACM, 42(2), 321–328. https://doi.org/10.1145/201019.201022