Holm–de Lichtenberg–Thorup Dynamic Connectivity Algorithm

The Holm–de Lichtenberg–Thorup Dynamic Connectivity Algorithm is a deterministic fully dynamic graph data structure introduced by Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup in 1998 (published in the Journal of the ACM in 2001) that maintains the connected components of an undirected graph G = (V, E) subject to an online sequence of edge insertions, edge deletions, and pairwise connectivity queries. For a graph on n = |V| vertices, the algorithm supports each edge insertion and deletion in O(log² n) amortized time and answers whether any two vertices u, v ∈ V reside in the same connected component in O(log n / log log n) worst-case time. Prior to this result, deterministic dynamic connectivity required O(√n) time per update via Frederickson's topology trees and Eppstein, Galil, Italiano, and Nissenzweig's sparsification technique, while polylogarithmic O(log³ n) bounds were known only for randomized Las Vegas algorithms invented by Monika Rauch Henzinger and Valerie King (1995). By organizing the edges of G into a logarithmic hierarchy of nested spanning forests represented by Euler tour trees and charging failed replacement-edge searches to monotonic level promotions, Holm, de Lichtenberg, and Thorup achieved the first deterministic polylogarithmic update bounds for dynamic connectivity, dynamic minimum spanning forest, dynamic 2-edge connectivity, and dynamic biconnectivity.

A fully dynamic graph connectivity data structure maintains an undirected graph G = (V, E) on a fixed vertex set V of cardinality n under three operations:

• Insert(u, v): Add the undirected edge e = (u, v) to E.
• Delete(u, v): Remove the undirected edge e = (u, v) from E.
• Connected(u, v): Return true if there exists a path between u and v in G, and false otherwise.

When only edge insertions are permitted (the incremental setting), the classic disjoint-set data structure with union by rank and path compression processes updates and queries in O(α(m, n)) amortized time. In the fully dynamic setting, however, deleting an edge produces a fundamental asymmetry. The data structure maintains a spanning forest F ⊆ E of G containing one spanning tree for each connected component. Inserting a non-tree edge or deleting a non-tree edge e ∈ E \ F does not change the connected components of F. Conversely, deleting a tree edge e ∈ F splits its spanning tree T into two smaller subtrees T₁ and T₂. To restore the spanning forest invariant, the algorithm must determine whether E \ F contains a replacement edge e′ = (x, y) with x ∈ V(T₁) and y ∈ V(T₂) that reconnects the two halves. Scanning all incident non-tree edges of T₁ naively can take Ω(m) time per deletion if most edges inspected turn out to have both endpoints inside T₁ rather than crossing the cut between T₁ and T₂.

The central innovation of the Holm–de Lichtenberg–Thorup algorithm is to assign every edge e ∈ E an integer level ℓ(e) ∈ {0, 1, …, L}, where L = ⌊log₂ n⌋. Newly inserted edges always begin at level 0, and over the course of edge deletions an edge's level can only increase, up to at most L.

For each level i ∈ {0, 1, …, L}, let E_i = {e ∈ E : ℓ(e) ≥ i} denote the subset of edges of level at least i, and let G_i = (V, E_i) be the corresponding subgraph. These subgraphs form a nested sequence:

G = G₀ ⊇ G₁ ⊇ G₂ ⊇ … ⊇ G_L.

correspondingly, the algorithm maintains a hierarchy of nested spanning forests F = F₀ ⊇ F₁ ⊇ F₂ ⊇ … ⊇ F_L, where F_i = F ∩ E_i is a spanning forest of G_i. The level assignments and spanning forests satisfy two structural invariants at all times:

1. Invariant 1 (Maximum Component Size at Level i): Every connected component (tree) of F_i contains at most ⌊n / 2ⁱ⌋ vertices. Because a connected component at level L = ⌊log₂ n⌋ can have at most ⌊n / 2^L⌋ = 1 vertex, no tree edge can ever exceed level L − 1, and every edge e ∈ E satisfies 0 ≤ ℓ(e) ≤ L.
2. Invariant 2 (Nested Spanning Forest Optimality): F₀ is a maximum-level spanning forest of G₀ = G, meaning that if all edges are weighted by their level ℓ(e), then F₀ is a maximum-weight spanning forest. Equivalently, there is no non-tree edge e = (u, v) ∈ E \ F whose level ℓ(e) = i is strictly less than the minimum level of any tree edge along the unique path P_F(u, v) in F; in particular, the endpoints u and v of a level-i non-tree edge are already connected within F_i.

Invariant 2 guarantees that if a tree edge e ∈ F at level ℓ(e) = i is deleted, no replacement edge can exist at any level j > i, because the endpoints of e were not connected in F_i+1 prior to the deletion. Therefore, the search for a replacement edge need only examine candidate non-tree edges at levels i, i − 1, …, 0 in descending order.

To execute tree splits, tree links, and incidence searches across all L + 1 levels efficiently, the algorithm represents each spanning forest F_i using Euler tour trees (ET-trees), originally introduced by Henzinger and King and closely related to Sleator–Tarjan link–cut trees.

Euler Tour Encoding of Dynamic Trees

For each tree T in the forest F_i, replacing every undirected edge {u, v} ∈ T with two oppositely directed arcs (u, v) and (v, u) produces a directed Eulerian multigraph. An Euler tour of T is a cyclic sequence of 2|V(T)| − 1 vertex visits obtained by performing a depth-first traversal of T and recording a vertex each time it is entered or re-entered. Storing this cyclic sequence in a balanced search tree allows splitting a tree when an edge is deleted or concatenating two trees when a replacement edge is inserted via a constant number of balanced-tree split and join operations.

• Forest F₀ (Query Forest): To achieve O(log n / log log n) query time, the Euler tour trees of the top-level spanning forest F₀ are implemented as B-trees with branching factor Θ(log n). Determining whether u and v are connected in G reduces to climbing from the representative nodes of u and v to the roots of their respective B-trees in F₀, which requires O(log n / log(log n)) = O(log n / log log n) steps.
• Forests F_i for 0 ≤ i ≤ L (Search Forests): Each Euler tour tree in F_i is implemented as a binary balanced search tree (such as a red–black tree or weight-balanced tree) of height O(log n). Every node in the ET-tree of F_i maintains two auxiliary boolean flags and aggregate counters:
  1. Whether the subtree beneath that ET-node contains any vertex incident to a level-i tree edge (used in F₀ to locate tree edges of level i).
  2. Whether the subtree beneath that ET-node contains any vertex incident to a level-i non-tree edge (used in F_i to locate candidate replacement edges at level i).

Because these flags are aggregated upward in the balanced binary search tree, the algorithm can find the next level-i tree edge or the next incident level-i non-tree edge in a component of F_i in O(log n) worst-case time, and can report the total number of vertices |V(T)| in any component T of F_i in O(1) time by reading the subtree size at the root of T's ET-tree.

Edge Insertion and Non-Tree Edge Deletion

When Insert(u, v) is invoked on a new edge e = (u, v), the algorithm assigns ℓ(e) = 0. It queries the Euler tour trees of F₀ in O(log n) time to check whether u and v already belong to the same connected component:

• If u and v are in different components of F₀, then e is inserted as a tree edge into F₀ by joining the Euler tour trees of u and v in O(log n) time.
• If u and v are already in the same component of F₀, then e is added as a level-0 non-tree edge to the incidence lists of u and v, updating the aggregate non-tree incidence flags in F₀ in O(log n) time.

When Delete(u, v) is invoked on a non-tree edge e ∈ E \ F at level i = ℓ(e), e is simply removed from the level-i non-tree incidence lists of u and v in F_i in O(log n) time, requiring no structural change to any spanning forest.

Tree Edge Deletion and Iterative Level Promotion

When Delete(u, v) removes a tree edge e ∈ F with level ℓ(e) = k, removing e splits the unique tree containing e in each forest F_k, F_k−1, …, F₀ into two subtrees. The algorithm then invokes Replace(u, v, i) for i = k, k − 1, …, 0 in descending order until either a replacement edge is found or level 0 is exhausted:

1. Select the Smaller Component: At level i, removing e has split its former level-i tree into two subtrees T_u and T_v in F_i. By comparing their vertex counts in O(1) time, relabel u and v if necessary so that |V(T_u)| ≤ |V(T_v)|. Because T_u ∪ T_v was a valid component of F_i prior to deletion, Invariant 1 ensures |V(T_u)| + |V(T_v)| ≤ ⌊n / 2ⁱ⌋, which implies that the smaller half satisfies:

|V(T_u)| ≤ ⌊n / 2ⁱ⁺¹⌋.

1. Promote Tree Edges of T_u to Level i + 1: Because |V(T_u)| ≤ ⌊n / 2ⁱ⁺¹⌋, the entire subtree T_u is now small enough to satisfy Invariant 1 at level i + 1. Using the tree-edge incidence flags in F₀, the algorithm locates every level-i tree edge f ∈ E(T_u), increments its level to ℓ(f) = i + 1, and inserts f into the forest F_i+1, taking O(log n) time per promoted tree edge.
2. Inspect Level-i Non-Tree Edges Incident to T_u: Using the non-tree incidence flags in the ET-tree of T_u at level i, the algorithm iteratively extracts each level-i non-tree edge f = (x, y) with x ∈ V(T_u) in O(log n) time and checks whether its other endpoint y lies in T_v:
   • Case A (Internal Edge, y ∈ V(T_u)): Both endpoints of f lie inside T_u, so f does not reconnect T_u and T_v. Because both endpoints belong to T_u (which has size at most ⌊n / 2ⁱ⁺¹⌋), the algorithm promotes f to level i + 1 by setting ℓ(f) = i + 1 and moving f to the non-tree incidence lists of F_i+1 in O(log n) time, then continues searching the remaining level-i non-tree edges of T_u.
   • Case B (Replacement Edge Found, y ∈ V(T_v)): The edge f crosses the cut between T_u and T_v. The algorithm converts f from a level-i non-tree edge into a level-i tree edge, links T_u and T_v across all forests F_i, F_i−1, …, F₀ using O(i + 1) = O(log n) ET-tree join operations of cost O(log n) each, and terminates the search immediately without inspecting any further edges or descending to level i − 1.
3. Descent on Exhaustion: If all level-i non-tree edges incident to T_u are promoted to level i + 1 without finding a replacement edge, then no replacement edge exists at level i. If i > 0, the algorithm decrements i to i − 1 and repeats the procedure; if i = 0, then G has become disconnected across (u, v) and the deletion finishes.

The O(log² n) amortized update bound follows from a potential-function charging argument tracking edge levels:

• Insertion Cost: Inserting an edge performs at most O(1) ET-tree operations in F₀, costing O(log n) worst-case time.
• Promotion Charging: Every time a tree edge or non-tree edge f is inspected and fails to serve as the terminal replacement edge during Replace, its level ℓ(f) increases by 1 (from i to i + 1). Because each promoted edge is moved in its ET-tree in O(log n) time and an edge's level can increase at most L = ⌊log₂ n⌋ times before it is deleted, the total work spent promoting a single edge over its entire lifetime in G is at most O(L · log n) = O(log² n).
• Successful Replacement and Structural Overhead: During a single Delete operation, at most one non-tree edge is converted into a replacement tree edge without being promoted. Reconnecting the forests F_i, …, F₀ with this single replacement edge requires at most L + 1 = O(log n) ET-tree join operations, each taking O(log n) time, for a total of O(log² n) structural overhead per deletion.

Summing the O(log² n) lifetime promotion budget charged upon edge insertion with the O(log² n) per-deletion structural overhead yields an amortized runtime of O(log² n) per edge insertion and deletion.

In the same 2001 monograph, Holm, de Lichtenberg, and Thorup extended their hierarchical level-promotion framework to three fundamental problems:

1. Dynamic Minimum Spanning Forest: By ordering candidate replacement edges within each level i by ascending edge weight and maintaining minimum-weight path queries on the spanning forest via dynamic trees (combining Dixon–Rauch–Tarjan MST verification concepts with dynamic tree data structures), the algorithm maintains the minimum spanning forest of a weighted undirected graph in O(log⁴ n) amortized time per edge insertion or deletion.
2. Dynamic 2-Edge Connectivity: An undirected graph is 2-edge-connected along a tree path P_F(u, v) if and only if every tree edge on P_F(u, v) is covered by at least one non-tree edge (compare with offline depth-first search bridge detection). By maintaining cover levels on tree paths and promoting uncovering edges across L = ⌊log₂ n⌋ levels whenever a bridge check occurs, the algorithm maintains 2-edge connectivity in O(log⁴ n) amortized update time and O(log n / log log n) query time.
3. Dynamic Biconnectivity: Generalizing path coverings from single tree edges to pairs of adjacent tree edges around articulation points yields a deterministic O(log⁵ n) amortized update time for fully dynamic biconnectivity (2-vertex connectivity).

1. Holm, J., de Lichtenberg, K., & Thorup, M. (2001). Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4), 723–760. https://doi.org/10.1145/502090.502095
2. Henzinger, M. R., & King, V. (1999). Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4), 502–516. https://doi.org/10.1145/320211.320215
3. Thorup, M. (2000). Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC) (pp. 343–350). https://doi.org/10.1145/335305.335345
4. Wulff-Nilsen, C. (2013). Faster deterministic fully-dynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1757–1769). https://doi.org/10.1137/1.9781611973105.126
5. Eppstein, D., Galil, Z., Italiano, G. F., & Nissenzweig, A. (1997). Sparsification—a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5), 669–696. https://doi.org/10.1145/265910.265914