xi. Dominator Tree

In a directed graph with root $r$, $u$ dominates $v$ if every path from $r$ to $v$ passes through $u$. The strict dominators of $v$ form a chain; the closest one is the immediate dominator $\text{idom}(v)$, and these edges form the dominator tree: $u$ dominates $v$ iff $u$ is an ancestor of $v$ in it. “Which vertices become unreachable if $x$ is deleted” = $x$‘s subtree. Lengauer–Tarjan computes it in $O(m\log n)$ (or $O(m\alpha )$).

Proof: dominators of $v$ form a chain

Let $a\ne b$ both strictly dominate $v$ and suppose neither dominates the other: there are paths $Q_a$ from $r$ to $a$ avoiding $b$ and $Q_b$ from $r$ to $b$ avoiding $a$. Take any path $P$ from $r$ to $v$; it contains both $a$ and $b$. If the last occurrence of $a$ on $P$ comes after the last occurrence of $b$, then $Q_a$ followed by the part of $P$ after that last $a$ is an $r$–$v$ walk avoiding $b$, contradicting that $b$ dominates $v$; symmetrically in the other case. So any two strict dominators are comparable, they form a chain, and the deepest one is $\text{idom}(v)$; making it $v$‘s parent gives a tree whose ancestor relation is dominance.

Lengauer–Tarjan

DFS from $r$ with preorder numbers. The semidominator $\text{sdom}(v)$ is the smallest-numbered $u$ with a path $u⇝v$ whose internal vertices are all numbered higher than $v$. Compute sdom in reverse preorder with a link-eval DSU (path compression carrying the minimum sdom), then convert to idom with the bucket rule.

struct Dominator {                                        // vertices 0..n-1
    int n, t = 0; vector<vector<int>> g, rg, bucket; vector<int> id, rev, par, sdom, dom, dsu, lab;
    Dominator(int n) : n(n), g(n), rg(n), bucket(n), id(n, -1), rev(n), par(n), sdom(n), dom(n), dsu(n), lab(n) {}
    void addEdge(int u, int v) { g[u].push_back(v); }
    void dfs(int u) {                                     // recursive; depth = DFS depth
        id[u] = t; rev[t] = u; lab[t] = sdom[t] = dsu[t] = t; t++;
        for (int w : g[u]) { if (id[w] < 0) { dfs(w); par[id[w]] = id[u]; } rg[id[w]].push_back(id[u]); }
    }
    int find(int u, int x = 0) {                          // link-eval with path compression
        if (u == dsu[u]) return x ? -1 : u;
        int v = find(dsu[u], x + 1);
        if (v < 0) return u;
        if (sdom[lab[dsu[u]]] < sdom[lab[u]]) lab[u] = lab[dsu[u]];
        dsu[u] = v;
        return x ? v : lab[u];
    }
    vector<int> build(int root) {                         // idom of every vertex, root -> root, unreachable -> -1
        dfs(root);
        for (int i = t - 1; i >= 0; i--) {
            for (int w : rg[i]) sdom[i] = min(sdom[i], sdom[find(w)]);
            if (i) bucket[sdom[i]].push_back(i);
            for (int w : bucket[i]) { int v = find(w); dom[w] = sdom[v] == sdom[w] ? sdom[w] : v; }
            if (i) dsu[i] = par[i];
        }
        for (int i = 1; i < t; i++) if (dom[i] != sdom[i]) dom[i] = dom[dom[i]];
        vector<int> res(n, -1); res[root] = root;
        for (int i = 1; i < t; i++) res[rev[i]] = rev[dom[i]];
        return res;
    }
};

Proof sketch: semidominators and the idom rule

Number vertices by DFS preorder. (1) $\text{sdom}(w)=\min (\{v:v\to w,v<w\}\cup \{\text{sdom}(u):u>w,u\text{ is an ancestor of some }v\text{ with }v\to w\})$: a semidominator path either is a single edge from a smaller vertex, or its last internal vertex chain lies in the DFS subtree of some $u>w$ that is an ancestor of the predecessor (DFS paths property: any path from a smaller to a larger vertex passes through a common ancestor). Processing $w$ in decreasing order, linked vertices are exactly those $>w$ already processed, so find over the DSU forest (a sub-forest of the DFS tree) returns the vertex with minimum sdom on the tree path, giving (1). (2) For $w\ne r$, let $u$ be the vertex with minimum $\text{sdom}$ on the tree path from $\text{sdom}(w)$ (exclusive) to $w$ (inclusive). If $\text{sdom}(u)=\text{sdom}(w)$ then $\text{idom}(w)=\text{sdom}(w)$; otherwise $\text{idom}(w)=\text{idom}(u)$. This is Lengauer–Tarjan’s main theorem: any path from $r$ to $w$ avoiding $\text{sdom}(w)$ would have to enter the tree path below it via a vertex whose semidominator is smaller, which the minimum rules out in the first case. Buckets evaluate the path minimum exactly when all vertices of that path have been linked, and the final top-down pass resolves the deferred $\text{idom}(u)$.

Other methods

• Iterative dataflow (Cooper–Harvey–Kennedy): in reverse postorder, repeat $\text{idom}(v)=$ intersection of the idoms of its processed predecessors (walking two pointers up by postorder number) until nothing changes. Very short and fast on real-world graphs, $O(nm)$ worst case — and on a reducible flow graph (the structured, no-goto-into-a-loop-body case that essentially all compiler-generated and contest-constructed graphs are) it provably converges in at most $d+3$ passes, where $d$ is the loop nesting depth, which is why it’s fast in practice despite the worst case.
• DAG: in topological order, $\text{idom}(v)$ = LCA (in the partially built tree) of all predecessors of $v$; with binary lifting $O(m\log n)$.
• Undirected connected graphs: there’s no useful dominator tree here in general — “every path from $r$ passes through $u$” is rarely true once the graph has cycles reachable both ways, so use the block-cut tree (Bridges and Biconnectivity) instead of forcing a directed concept onto an undirected graph.
• Post-dominators: the same on the reversed graph from the exit vertex.
• Edge dominators / bridges in the directed sense: subdivide each edge with a midpoint vertex; an edge dominates $v$ iff its midpoint does.
• Alstrup et al. / Buchsbaum et al.: $O(n+m)$ is achievable but the constants and implementation complexity make it purely theoretical interest for contests — Lengauer–Tarjan or CHK is always the right call in practice.

Uses

Question	Answer
vertices unreachable from $r$ after deleting $x$	subtree of $x$ (minus nothing else)
is $x$ on every $r$–$v$ path?	$x$ is an ancestor of $v$
for each $v$, number of vertices whose deletion cuts $v$ off	depth of $v$ in the dominator tree
”must pass” vertices between $r$ and $t$	path from $t$ to the root
compilers: SSA $\varphi$-placement	dominance frontiers from the tree