Dynamic Graph Connectivity, in depth: spanning forests, smaller-side replacement search, HDT levels and choosing the right variant

The variants and which one you have

The variants differ in which updates are allowed and whether you see the future. Picking the wrong one is the most common and most expensive mistake, because the fully dynamic online structures are an order of magnitude more complex than the others.

Two lessons sit in that table. First, if your graph is a forest, you do not need connectivity machinery at all; a dynamic tree answers it directly. Second, a surprising number of production systems can tolerate answers that are a few seconds stale, and for them a periodic rebuild beats every clever structure on simplicity. The hard case is the remaining one: arbitrary graphs, deletions, and answers that must be exact right now.

Why deletions are hard: forests and replacement edges

The central idea of every online method is to maintain a spanning forest F of the current graph: a set of edges with no cycles that connects exactly what the graph connects. Two vertices are connected in the graph if and only if they are in the same tree of F. Every graph edge is therefore either a tree edge (in F) or a non-tree edge, which we will call a spare: it closes a cycle and adds no connectivity.

Insertions are easy. If the endpoints are already in one tree, the new edge is a spare. Otherwise it joins two trees and becomes a tree edge. Deleting a spare is also easy: it carried no connectivity, so nothing changes. The only hard operation is deleting a tree edge. Its tree splits into two pieces, and the graph may or may not still connect them. It does if and only if some spare edge has one endpoint in each piece; such an edge is a replacement, and promoting it to a tree edge restores the forest. So dynamic connectivity reduces to one question: after a tree split, find a replacement edge quickly, or prove none exists.

The naive search scans every spare edge, which costs O(m) per deletion. The trick that makes it practical is to search from the smaller piece. Any replacement must have an endpoint in the smaller piece, so scanning its spares is enough. And because you do not know which piece is smaller in advance, you walk both pieces in lockstep, one vertex at a time each, and stop as soon as either walk runs out. The work is then proportional to the smaller side, not the larger.

A structure you can ship

The structure below keeps the forest as adjacency sets, spare edges in a second set of adjacency sets, and a component id per vertex so that queries are a single comparison. Insertion between two trees relabels the smaller one, which is the same union-by-size argument that bounds union-find: a vertex is relabelled at most log₂ n times during insertions alone.

from itertools import count

class DynamicConnectivity:
    """Spanning forest + smaller-side replacement search. Simple graphs only."""

    def __init__(self, n):
        self.tree = [set() for _ in range(n)]      # spanning-forest edges
        self.extra = [set() for _ in range(n)]     # spare (non-tree) edges
        self.comp = list(range(n))                 # component id per vertex
        self.size = {i: 1 for i in range(n)}
        self.ids = count(n)

    def connected(self, u, v):
        return self.comp[u] == self.comp[v]

    def _tree_walk(self, root):
        seen, stack = {root}, [root]
        while stack:
            x = stack.pop()
            yield x
            for y in self.tree[x]:
                if y not in seen:
                    seen.add(y)
                    stack.append(y)

    def insert(self, u, v):
        if u == v or v in self.tree[u] or v in self.extra[u]:
            return
        cu, cv = self.comp[u], self.comp[v]
        if cu == cv:                                # closes a cycle: keep as spare
            self.extra[u].add(v); self.extra[v].add(u)
            return
        if self.size[cu] < self.size[cv]:          # relabel the smaller tree
            u, v, cu, cv = v, u, cv, cu
        for x in list(self._tree_walk(v)):
            self.comp[x] = cu
        self.size[cu] += self.size.pop(cv)
        self.tree[u].add(v); self.tree[v].add(u)

    def delete(self, u, v):
        if v in self.extra[u]:                      # spare edge: O(1)
            self.extra[u].discard(v); self.extra[v].discard(u)
            return
        if v not in self.tree[u]:
            return
        self.tree[u].discard(v); self.tree[v].discard(u)
        walks, found, done = [self._tree_walk(u), self._tree_walk(v)], [[], []], None
        while done is None:                         # lockstep until one side ends
            for side in (0, 1):
                x = next(walks[side], None)
                if x is None:
                    done = side
                    break
                found[side].append(x)
        small = set(found[done])
        for x in small:                             # replacement edge?
            for y in self.extra[x]:
                if y not in small:
                    self.extra[x].discard(y); self.extra[y].discard(x)
                    self.tree[x].add(y); self.tree[y].add(x)
                    return
        old, new = self.comp[u], next(self.ids)     # genuinely split
        for x in small:
            self.comp[x] = new
        self.size[new] = len(small)
        self.size[old] -= len(small)

Test it the way every dynamic structure should be tested: thousands of random insert, delete and query sequences on small graphs, each query checked against a plain BFS over the current edge set. This implementation passes 300 such runs of 200 operations each. The cost profile is honest: queries O(1), spare deletions O(1), insertions amortised O(log n) relabels, and a tree-edge deletion costs the size of the smaller piece plus the spare degree of its vertices. That last term has no worst-case bound: a dense cluster that keeps losing the same bridge will be rescanned every time. HDT exists to fix exactly that.

Worked example: six vertices, two deletions

Take six vertices and insert, in order, the edges 0-1, 1-2, 2-0, 2-3, 3-4, 4-5 and 3-5. The forest takes 0-1, 1-2, 2-3, 3-4 and 4-5; edges 2-0 and 3-5 arrive when their endpoints are already connected, so they become spares. All six vertices share component 0.

Now delete 2-3. It is a tree edge, so the tree splits into {0, 1, 2} and {3, 4, 5}. The lockstep walk visits 2 and 3, then 1 and 4, then 0 and 5, and the walk from 2 is the first to report exhaustion, so {0, 1, 2} is the side we search. Its only spare is 2-0, which stays inside the set. No replacement exists: the side is relabelled to a fresh id 6, sizes become 3 and 3, and connected(0, 4) now returns False.

Next delete 3-4. The tree {3, 4, 5} splits into {3} and {4, 5}; the walk from 3 ends after one vertex. Vertex 3 has the spare 3-5, whose other endpoint is outside {3}, so 3-5 is promoted to a tree edge and nothing is relabelled. connected(3, 4) still returns True, through 3-5-4. Notice that the search touched one vertex and one edge, although the graph had six of each: that locality is the whole point.

HDT: levels that make failed searches pay

The structure of Holm, de Lichtenberg and Thorup (published in the Journal of the ACM in 2001) guarantees amortised O(log² n) time per update and O(log n / log log n) per query. It keeps the smaller-side search but adds a way to make every failed scan pay for itself. Each edge carries a level between 0 and L = floor(log₂ n). Let F_i be the subforest of tree edges with level at least i, so F₀ is the whole spanning forest. Two invariants hold at all times:

1. Every tree of F_i has at most n / 2ⁱ vertices.
2. F₀ is a maximum spanning forest with respect to levels: a spare edge of level i always has both endpoints in the same tree of F_i.

Insertion puts the new edge at level 0. Deleting a tree edge of level l runs the search from level l down to 0:

delete tree edge e = (u, v) at level l:
    remove e from F_0 .. F_l
    for i = l down to 0:
        Tu, Tv = trees of u and v in F_i
        T = the smaller of Tu, Tv              # |T| <= n / 2^(i+1)
        raise every level-i tree edge of T to level i+1      # invariant 1 still holds
        for each level-i spare edge f incident to T:
            if f has its other endpoint in the other tree:
                make f a tree edge at level i (insert into F_0 .. F_i)
                return                         # reconnected
            else:
                raise f to level i+1           # both ends inside T, which fits in F_(i+1)
    # no replacement at any level: the component has genuinely split

The amortisation is the elegant part. Edge levels only ever increase and are capped at log₂ n, so over its lifetime each edge is raised at most log n times. Every spare edge examined without success is raised, so it is paid for by that budget. Each tree is stored as an Euler tour tree, a balanced search tree over the tree's Euler tour (see Euler tour on trees), which supports cut, link and the walk to find level-i edges in O(log n) each. That gives O(log n) raises times O(log n) per raise. A matching lower bound of Omega(log n) per operation, due to Patrascu and Demaine, shows the gap to optimal is only one logarithmic factor.

In practice HDT is rarely implemented from scratch: one Euler tour tree per level, with subtree flags marking where level-i edges live, is a few thousand lines in a systems language. Experimental studies have found that simpler heuristics, like the one above, are competitive on many real graphs; HDT earns its complexity when adversarial or repetitive deletion patterns would otherwise rescan the same dense region again and again.

Engineering notes

A few engineering choices matter more than the asymptotic bound. Use integer vertex ids and store adjacency in arrays or hash sets keyed by id; the constant factors of the search dominate. Treat parallel edges explicitly, either by rejecting them as the code above does or by keeping a multiplicity count, because a deletion of one copy must not cut the forest. Make the component id stable for consumers, or expose only connected(), since relabelling changes ids on every split and merge. And log the size of the searched side on every tree-edge deletion: its distribution is the best early warning that your workload has drifted towards the bad case.

Failure modes

• Using union-find for deletions. Teams add a 'remove' that deletes a vertex from its set, which silently leaves the rest of the set wrongly merged. Union-find cannot split; if you see deletions, you need one of the other rows of the table.
• Parallel edges. Two links between the same switches are common. Without multiplicity, deleting one copy cuts a tree edge whose twin still exists.
• Unbounded deletion scans. A hub vertex with ten thousand spares makes every split near it scan all of them. Monitor scanned edges per deletion.
• Recursive traversal. A recursive DFS on a long path overflows the stack; use an explicit stack as above.
• Stale component ids leaked to callers. Ids are internal and change on relabel; callers caching them will compare the wrong things.

Trade-offs

The smaller-side structure is short, easy to test and fast on graphs where tree-edge deletions are rare or local, which covers most network-topology and dependency-graph workloads. HDT buys a guaranteed amortised bound for roughly fifty times the code. Offline methods are simpler than both but need the whole sequence. Periodic rebuilds are trivial and parallelise well but answer from the past. Choose by asking two questions in order: do I know the future, and can I tolerate stale answers? Only if both answers are no do you need an online fully dynamic structure, and even then start with the simple one and measure.

What to do next

1. Classify your workload against the table: insert-only, forest-only, offline, stale-tolerant or fully dynamic online.
2. If it is insert-only, use union-find and stop.
3. Otherwise implement the smaller-side structure above and its random brute-force test before anything more ambitious.
4. Add multiplicity counts if your graph can have parallel edges.
5. Instrument tree-edge deletions with the searched side size and scanned spare count.
6. Replay a day of production operations and read the p99 of that metric.
7. Only if the tail is unacceptable, move to HDT or an existing library implementation.