Lengauer-Tarjan Algorithm

Purpose: Compute the dominator tree of a flow graph in $O(E\alpha (E,V))$ (or $O(E\log V)$ with the simple version) — the standard algorithm in every optimising compiler.

Dominators

In a directed graph with entry $r$, vertex $u$ dominates $v$ if every path $r\to v$ passes through $u$. The immediate dominator $\mathrm{idom}(v)$ is the closest such $u\ne v$. The idom relation forms a tree rooted at $r$ — the dominator tree.

Algorithm

1. DFS from $r$, numbering vertices in preorder as $\mathrm{1..}n$. Record the DFS tree and parent[].
2. Semidominators. Define
   $\mathrm{sdom}(v)=\min \{\mathrm{dfn}(u):\exists \text{ path }u=v_0\to v_1\to \cdots \to v_k=v\text{ with }\mathrm{dfn}(v_i)>\mathrm{dfn}(v)\text{ for }0<i<k\}.$
   In words: the highest-numbered vertex from which you can reach $v$ through vertices all numbered higher than $v$. Compute these in reverse DFS order using a link-eval structure (a DSU with path compression that also tracks the minimum sdom along the compressed path).
3. Implicit idom. Bucket each $v$ under $\mathrm{sdom}(v)$. When processing $w$, for each $v$ in its bucket, find $u=\mathrm{eval}(v)$ — the vertex on the path with minimum sdom. Then
   $\mathrm{idom}(v)=\{\begin{array}{ll}\mathrm{sdom}(v)& \text{if }\mathrm{sdom}(u)=\mathrm{sdom}(v)\\ u(\text{defer})& \text{otherwise.}\end{array}$
4. Final pass in DFS order fixes the deferred entries: $\mathrm{idom}(v)=\mathrm{idom}(u)$.

Complexity

Version	Time
Simple (path compression only)	$O(E\log V)$
Sophisticated (union by size + path compression)	$O(E\alpha (E,V))$
Iterative dataflow (Cooper-Harvey-Kennedy)	$O(VE)$ worst, near-linear in practice
Alstrup et al. / Buchsbaum et al.	$O(V+E)$

Space is $O(V+E)$ throughout.

Why the semidominator detour

Computing idom directly is hard because the definition quantifies over all paths. The semidominator is a relaxation that only looks at paths through higher-numbered vertices, which makes it computable by a single reverse-order sweep. The two-case rule in step 3 then converts sdom into idom exactly. This indirection is the whole trick, and the reason the algorithm looks mysterious the first time.

In a contest

Dominator trees appear rarely, but when they do the problem is usually “which vertices become unreachable if $x$ is removed” or “count vertices only reachable through $x$” — both are subtree questions on the dominator tree. The Cooper-Harvey-Kennedy iterative algorithm is ~30 lines and fast enough for contest sizes; keep Lengauer-Tarjan for when $E$ is large.

Variants / Use Cases

• Compiler SSA construction — dominance frontiers come straight from the dominator tree; this is the original and still main use
• Dominator Tree — the topic page
• Reachability under vertex deletion — “how many vertices become unreachable if $v$ fails”
• Post-dominators — run the same algorithm on the reversed graph from the exit node
• Control dependence — the combination of dominators and post-dominators
• DSU with path compression — the link-eval structure is a DSU variant carrying an aggregate