Gabow–Tarjan Linear-Time Union–Find

Gabow–Tarjan linear-time union–find is an algorithmic technique and data structure in computation and algorithms introduced by Harold N. Gabow and Robert E. Tarjan in 1985 (Journal of Computer and System Sciences) that solves a structured special case of the disjoint-set data structure (Union–Find) problem in deterministic O(m + n) linear time on a random-access machine (RAM). In the general disjoint-set problem, an algorithm maintains a partition of n elements under an arbitrary online sequence of n − 1 Union operations and m Find operations; Robert E. Tarjan (1975) proved that union-by-rank with path compression executes this sequence in O(m α(m, n) + n) time, where α(m, n) is the slow-growing functional inverse of Ackermann's function, and Michael L. Fredman and Michael E. Saks (1989) proved a matching Ω(m α(m, n)) cell-probe lower bound for unrestricted online unions. Gabow and Tarjan observed that in many combinatorial algorithms—including Tarjan's off-line lowest common ancestors algorithm, non-bipartite maximum matching via Edmonds's blossom algorithm, tree interval marking, and linear-time minimum spanning tree verification—the allowed unions are constrained to the edges of a static union tree T whose topology is known before the dynamic Link and Find sequence begins (or grows by incremental leaf additions). By partitioning T into connected microsets of size at most b = Θ(log log n) (or (1/2) log₂ n), maintaining a path-compressed macroset union–find structure over the O(n/b) microset roots, and encoding the internal topology and active edge mask of each microset inside a machine word for O(1) lookup-table evaluation ("Four Russians" paradigm), the Gabow–Tarjan method eliminates the α(m, n) factor and achieves O(m + n) linear complexity.

General Online Disjoint-Set Complexity

A disjoint-set data structure maintains a collection of pairwise disjoint dynamic sets S = {S₁, S₂, …, S_k} over a universe U of n elements under three primitives: MakeSet(x), which creates a singleton set {x}; Find(x), which returns the canonical representative of the unique set containing x; and Union(x, y), which merges the sets containing x and y.

When the sequence of Union operations is arbitrary and revealed online, linking trees by rank (or size) and applying path compression during every Find operation yields a total running time of Θ(m α(m, n) + n) for n MakeSet operations, at most n − 1 Union operations, and m Find operations. Here α(m, n) satisfies α(m, n) ≤ 4 for all practical input sizes, yet remains asymptotically unbounded as n → ∞. In 1979, Tarjan proved that any separable pointer-machine algorithm requires Ω(m α(m, n)) time in the worst case, and Fredman and Saks (1989) established in the cell-probe model with word size w = Θ(log n) that any data structure supporting arbitrary online Union and Find queries requires an amortized Ω(α(m, n)) memory probes per operation. Consequently, no general-purpose disjoint-set data structure on a RAM can break the inverse-Ackermann barrier when the pattern of unions is unrestricted.

Formulation of the Static Union-Tree Problem

Gabow and Tarjan (1985) recognized that in numerous graph and tree algorithms, there exists an underlying rooted tree T = (V, E_T) on n = |V| vertices, known in advance before the dynamic phase starts, that governs which elements may be merged. Initially, every vertex v ∈ V is an independent singleton set {v}, meaning every edge (v, p(v)) connecting v to its parent p(v) in T is inactive (unlinked). The structure supports two online operations interleaved in any order:

1. Link(v): Given a non-root vertex v ∈ V whose parent edge (v, p(v)) in T is inactive, activate the edge (v, p(v)), merging the connected subtree containing v with the connected subtree containing p(v) in T.
2. Find(v): Given any vertex v ∈ V, return the shallowest ancestor r of v in T reachable from v using only currently active (Linked) edges of T.

Because union operations only activate edges of the fixed tree T, every dynamic set at any moment corresponds to a connected subtree of T, and its canonical representative is uniquely defined as the root (highest ancestor in T) of that connected subtree. Gabow and Tarjan also formulated an incremental tree union–find extension in which T grows online via a third operation Grow(u, v) that attaches a new leaf vertex u as a child of an existing vertex v ∈ T. Because new vertices are only attached as leaves, the microset partition can be updated dynamically in O(1) amortized time per leaf addition, preserving the O(m + n) linear time bound.

Tree Partitioning Lemma

The foundational step of the Gabow–Tarjan algorithm is a bottom-up greedy clustering of the n-vertex union tree T into small connected subtrees called microsets (or microtrees), governed by a target cluster capacity parameter b ≥ 2 (chosen as b = ⌈log₂ log₂ n⌉ in the two-level macro–micro scheme, or b = ⌊(1/4) log₂ n⌋ when reducing directly to O(1) table lookups).

For any rooted tree T with n vertices and any integer parameter b ≥ 2, the vertex set V(T) can be partitioned in O(n) deterministic time into pairwise vertex-disjoint microsets M₁, M₂, …, M_k satisfying four invariants:

1. Bounded Cardinality: Every microset M_i contains at most b vertices (|M_i| ≤ b).
2. Subtree Connectivity and Root Uniqueness: Each microset M_i (together with the parent of its highest vertices) forms a rooted tree under a single designated microset root r(M_i) ∈ V(T), such that for every non-root vertex v ∈ M_i, its parent p(v) in T belongs to M_i or equals r(M_i).
3. Sublinear Number of Macro-Nodes: The total number of microsets k satisfies k ≤ 2n/b + 1 = O(n/b).
4. Linear-Time Construction: A single postorder depth-first traversal of T constructs all microsets and identifies their roots r(M_i) in O(n) worst-case time.

Postorder Greedy Clustering Procedure

The postorder partitioning algorithm computes for each vertex u ∈ V(T) the residual size s(u) of the unpartitioned descendants in its subtree:

• Initialize s(u) ← 1 for every vertex u ∈ V(T) and traverse T in bottom-up postorder.
• At vertex u, iterate through its children w₁, …, w_d, maintaining a running sum of residual child subtree sizes. Whenever adding the next child's residual component s(w_j) would cause the running cluster size at u to exceed b − 1, seal off the accumulated group of child subtrees as a completed microset M_i of size between b/2 and b rooted at r(M_i) = u, and reset the running accumulator at u to 1.
• After examining all children of u, if s(u) ≥ b/2, seal it off as a microset rooted at u and set s(u) ← 0; otherwise pass the residual subtree of size s(u) < b/2 upward to p(u). At the global root of T, any leftover vertices form one final microset of size at most b.

Because every sealed microset except possibly the last has cardinality at least b/2, the total number of microsets is bounded by k ≤ 2n/b + 1.

Macroset Union–Find and Compression Over Microset Roots

Once T is partitioned into k = O(n/b) microsets, let R = {r(M₁), …, r(M_k)} denote the set of microset roots (macro-nodes), where |R| ≤ 2n/b + 1. Whenever all edges along the path in T from a microset root r(M_i) up to its enclosing microset root r(M_j) become active, the macro-node r(M_i) is merged into r(M_j) inside a global macroset union–find structure maintaining the partition of R.

Because the macroset structure contains N_macro = |R| = O(n/b) elements, it undergoes at most N_macro − 1 = O(n/b) macro-level Union operations across the entire execution. Using standard union-by-rank and path compression on the O(n/b) macro-nodes, M_macro ≤ m macro-level Find operations and O(n/b) macro-level Union operations take time:

Because α(m, n) ≤ log log n for all n ≥ 4, setting b = Θ(log log n) (or b = ⌊(1/4) log₂ n⌋ in a single-tier RAM lookup scheme) ensures that the entire macroset union–find cost—including all path compressions among microset roots—collapses to O(m + n) linear time.

The Four Russians Encoding for Microsets

To achieve O(1) worst-case time for operations inside each microset M_i of size s = |M_i| ≤ b, Gabow and Tarjan apply the Four Russians (Arlazarov, Dinic, Kronrod, and Faradžev, 1970) table-lookup paradigm. Within a microset M_i of s ≤ b vertices, each vertex is assigned a local preorder index in {0, 1, …, s − 1}. Three compact integers specify the topology and dynamic state of M_i:

1. Tree Topology Code (tau): Any rooted ordered tree on s ≤ b vertices is uniquely encoded by its balanced-parenthesis Euler tour bitstring of length 2s ≤ 2b bits (0 for a downward step, 1 for an upward step), yielding at most 4^b microtree shapes.
2. Active Edge Bitmask (mask): The dynamic state of M_i is stored as a b-bit integer mask ∈ {0, 1}^b, where the j-th bit is 1 if the edge from local vertex j to its parent in M_i is currently active (Linked), and 0 otherwise.
3. Local Vertex Index (j): The query vertex inside M_i is given by its local preorder index j ∈ {0, …, b − 1}.

Precomputed Lookup Table and Constant-Time Micro-Operations

During global initialization, the algorithm builds a shared lookup table *MicroFind*[tau][mask][j] storing the local index a ∈ {0, …, b − 1} of the highest ancestor of j inside microtree tau reachable using only edges whose bits are set to 1 in mask. Choosing b = ⌊(1/4) log₂ n⌋ bounds the total number of table entries to:

Thus, MicroFind occupies o(n) words of memory and is precomputed in o(n) deterministic time. With MicroFind initialized, the two operations execute in O(1) microset time:

• Executing Link(v): For vertex v in microset M_i with local index j, set the j-th bit of M_i.*mask* via a bitwise OR (M_i.*mask* ← M_i.*mask* ∨ (1 ≪ j)) in O(1) time. If activating v's edge connects a child microset root up to r(M_i) (checked in O(1) time via MicroFind), trigger a macroset Union between the two microset roots.
• Executing Find(v): Query a ← *MicroFind*[M_i.*tau*][M_i.*mask*][j] in O(1) time. If a ≠ 0, the active path from v stops inside M_i below r(M_i), so return the global vertex ID of a in O(1) time without consulting the macroset structure. If a = 0 (v reaches r(M_i)), call macro-level Find_macro(r(M_i)) to locate the highest connected microset root r(M_p), and perform one final O(1) MicroFind lookup inside the microset containing r(M_p).

Word-Level Parallelism Without Lookup Tables

On a 64-bit word RAM where b ≤ w, each vertex j inside M_i can store a static b-bit ancestor mask *AncMask*[j] identifying the edges on the path from j to r(M_i). Computing Blocked ← *AncMask*[j] ∧ (¬M_i.*mask*) isolates all inactive edges on j's ancestor path: if Blocked = 0, j reaches r(M_i); if Blocked ≠ 0, hardware Count Leading Zeros (CLZ / TZCNT) identifies the lowest inactive blocking edge in 3 CPU instructions without any external lookup table.

The table below compares the Gabow–Tarjan static union-tree algorithm against general and restricted disjoint-set structures.

Linear-Time Offline Lowest Common Ancestors (LCA)

In Tarjan's off-line lowest common ancestors algorithm (1979), given a rooted tree T on n vertices and m query pairs {(u_k, v_k)}, a depth-first traversal of T executes Union(u, p(u)) upon backtracking from each vertex u to its parent p(u), and answers LCA(u, v) via Find(u). Because every union merges a child u into its parent p(u) along an edge of the static input tree T, replacing general union–find with the Gabow–Tarjan static union-tree algorithm reduces the complexity of Tarjan's offline LCA algorithm from O((n + m) α(n + m, n)) to O(n + m) linear time.

Tree Path Compression and Offline Minimum

Given a rooted tree T on n vertices and m path-painting queries (u_k, a_k) that color every unpainted edge on the tree path from u_k up to ancestor a_k, maintaining a Gabow–Tarjan union-tree on T allows each query to jump directly over already-painted subpaths via y ← Find(x), paint the edge above y, and call Link(y) in O(m + n) total time. When T is a simple path of length n, this solves the off-line minimum problem and single-processor deadline scheduling in O(n) linear time.

Blossom Shrinking and Minimum Spanning Tree Verification

In Edmonds's blossom algorithm (1965) for maximum cardinality matching in general graphs, alternating search trees grow incrementally at leaves while odd cycles (blossoms) are contracted along tree paths. Gabow and Tarjan's incremental tree union–find maintains all blossom contractions during each augmenting-path phase in O(m + n) time, yielding an overall O(m √n) matching bound. Similarly, Dixon, Rauch, and Tarjan (1992) used the Gabow–Tarjan microset partition of a candidate spanning tree T to verify minimum spanning trees in deterministic O(m + n) linear time.

Why does the Fredman–Saks Ω(m α(m, n)) lower bound not rule out the Gabow–Tarjan O(m + n) algorithm?

The Fredman–Saks (1989) cell-probe lower bound applies to the general online disjoint-set problem, where an adversary can request Union(x, y) between any two arbitrary sets dynamically. In the Gabow–Tarjan problem, unions are restricted to edges of a fixed tree T known in advance (or grown incrementally at leaves). Knowing T allows the algorithm to partition T into connected microsets of size b ≤ (1/4) log₂ n so that every intra-microset union flips a single bit in a b-bit word rather than rewiring arbitrary pointers.

Can the Gabow–Tarjan algorithm run in O(m + n) time on a pure pointer machine without bit manipulation?

For online Link and Find queries on a static tree T, achieving O(m + n) time requires the RAM model's ability to index precomputed lookup tables (or execute bitwise operations) on b-bit microset masks. On a strict pointer machine where address arithmetic and bit manipulation are forbidden, Buchsbaum et al. (1998) showed that online tree union–find still requires Θ(m α(m, n) + n) time, although offline batches of tree queries can be solved in O(m + n) time.

How large are the microsets in practical 64-bit implementations?

On a 64-bit processor supporting hardware bitwise operations and single-cycle bit-scan instructions (LZCNT / TZCNT or CLZ), setting the microset capacity to b = 32 or b = 64 allows the active edge mask mask and every vertex's ancestor path mask *AncMask*[j] to fit inside a single 64-bit register. Under this broadword representation, no external lookup table is needed, and intra-microset Link and Find operations execute in 2 to 4 register instructions.

1. Gabow, H. N., & Tarjan, R. E. (1985). A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2), 209–221. https://doi.org/10.1016/0022-0000(85)90014-590014-5)
2. Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215–225. https://doi.org/10.1145/321879.321884
3. Tarjan, R. E. (1979). Applications of path compression on trees. Journal of the ACM, 26(4), 690–715. https://doi.org/10.1145/322154.322161
4. Fredman, M. L., & Saks, M. E. (1989). The cell probe complexity of dynamic data structures. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (STOC '89) (pp. 345–354). ACM. https://doi.org/10.1145/73007.73040
5. Dixon, B., Rauch, M., & Tarjan, R. E. (1992). Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6), 1184–1192. https://doi.org/10.1137/0221070