Holm-de Lichtenberg-Thorup Dynamic Connectivity

Purpose: Maintain the connected components of an undirected graph under both edge insertions and deletions, in $O({\log }^{2}n)$ amortized per update and $O(\log n/\log \log n)$ per connectivity query. Usually abbreviated HDT (2001).

The Difficulty

Insertions alone are easy — that is what DSU does in near-constant time. Deletions are the problem: removing a tree edge may or may not disconnect the graph, and finding a replacement edge requires searching the cut.

The Idea: edge levels

Assign every edge a level in $[0,\log n]$, maintaining two invariants:

1. Spanning forests are nested. $F_i$ = the spanning forest of edges at level $\ge i$; $F_0\supseteq F_1\supseteq \dots$
2. Level-$i$ components are small. Every connected component of $F_i$ has at most $n/2^i$ vertices.

Invariant 2 is the whole engine: it caps the number of times an edge can be promoted at $\log n$, which is where the amortization comes from.

Each forest $F_i$ is stored in an Euler tour tree so that link, cut, subtree size, and “find any non-tree edge incident to this subtree” are all $O(\log n)$.

Operations

• Insert $(u,v)$: give it level 0. If $u,v$ are in different components of $F_0$, add it to the forest; otherwise store it as a non-tree edge.
• Delete $(u,v)$: if it is a non-tree edge, just remove it. If it is a tree edge at level $\ell$, remove it from every $F_i$ with $i\le \ell$ and search for a replacement, from level $\ell$ downwards:
  • split the component into two parts; take the smaller one (guaranteed by invariant 2 to have $\le n/2^{i+1}$ vertices);
  • promote every level-$i$ tree edge in the smaller part to level $i+1$ — this is safe by invariant 2 and pays for itself;
  • scan the level-$i$ non-tree edges out of the smaller part. Each either connects to the other side (→ it is the replacement, done) or stays inside (→ promote it to level $i+1$ and continue).
• Query $\mathrm{connected}(u,v)$: are they in the same tree of $F_0$?

Complexity

• Update: $O({\log }^{2}n)$ amortized — each edge is promoted $O(\log n)$ times, each promotion costing $O(\log n)$
• Query: $O(\log n)$, or $O(\log n/\log \log n)$ with a $B$-tree-based Euler tour structure
• Space: $O(m+n\log n)$

The amortization argument

An edge’s level only ever increases, and it is bounded by $\log n$. A scan that fails to find a replacement always promotes the edge it examined, so the cost of failed scans is charged to promotions. A scan that succeeds ends the operation. Total promotions over $m$ updates: $O(m\log n)$, each $O(\log n)$. ∎

In a contest: use the offline version

If all queries are known in advance — which is nearly always the case in competitive programming — the segment tree on time approach is much simpler:

1. Each edge exists during a time interval; insert it into $O(\log q)$ nodes of a segment tree over the query timeline.
2. DFS the segment tree, uniting edges on the way down and rolling back on the way up, with a rollback DSU (union by size, no path compression).
3. Answer queries at the leaves.

$O((n+q)\log q\log n)$, about 60 lines, and no Euler tour trees. See Dynamic Connectivity.

Variants / Use Cases

• Dynamic MST — extend HDT with weights; $O({\log }^{4}n)$ amortized
• Dynamic bipartiteness / 2-edge-connectivity — same level machinery with extra bookkeeping
• Euler Tour Trees — the underlying structure
• Link-Cut Trees — handle path aggregates, which Euler tour trees cannot
• Frederickson — the earlier $O(\sqrt{m})$ worst-case approach