Dominator Tree

In a directed graph with a fixed entry $r$, vertex $u$ dominates $v$ if every path from $r$ to $v$ passes through $u$. Each $v$ has a unique immediate dominator $\mathrm{idom}(v)$ — its closest strict dominator — and these form a tree.

Basic facts

• $r$ dominates everything reachable from it.
• Dominance is a partial order; the dominators of $v$ form a chain from $r$ to $v$.
• $\mathrm{idom}(v)$ is the parent of $v$ in the dominator tree.
• The set of vertices dominated by $u$ is exactly $u$‘s subtree in the dominator tree.
• Unreachable vertices are simply excluded.

Algorithms

Method	Time	Difficulty
Iterative dataflow (Cooper-Harvey-Kennedy)	$O(VE)$ worst, near-linear in practice	easy — ~30 lines
Lengauer-Tarjan simple	$O(E\log V)$	hard
Lengauer-Tarjan sophisticated	$O(E\alpha (E,V))$	very hard
Alstrup et al.	$O(V+E)$	theoretical

The easy algorithm

Process vertices in reverse postorder, repeatedly intersecting dominator sets until a fixed point:

vector<int> idom, order, rpoNum;      // reverse postorder numbering
 
int intersect(int a, int b) {          // "closest common dominator"
    while (a != b) {
        while (rpoNum[a] > rpoNum[b]) a = idom[a];
        while (rpoNum[b] > rpoNum[a]) b = idom[b];
    }
    return a;
}
 
void computeIdom(int root) {
    idom.assign(n, -1);
    idom[root] = root;
    bool changed = true;
    while (changed) {
        changed = false;
        for (int u : order) {                     // reverse postorder, skip root
            if (u == root) continue;
            int newIdom = -1;
            for (int p : rpred[u]) {
                if (idom[p] == -1) continue;
                newIdom = (newIdom == -1) ? p : intersect(p, newIdom);
            }
            if (newIdom != -1 && idom[u] != newIdom) { idom[u] = newIdom; changed = true; }
        }
    }
}

This converges in very few iterations on real graphs and is what to write unless $E$ is enormous.

Special cases that are much easier

Graph	Dominator tree
DAG	process in topological order; $\mathrm{idom}(v)=\mathrm{LCA}$ of all predecessors in the partially built tree
Tree	the tree itself
Undirected connected	every vertex’s idom is its parent in any BFS/DFS tree only if… (in general, use the block-cut tree instead)
Reducible flow graph (structured code)	the iterative algorithm converges in $\le d+3$ passes where $d$ is the loop nesting depth

The DAG case is worth remembering: with a topological order and an incremental LCA structure, you get the dominator tree in $O(E\log V)$ with code you probably already have.

What it answers

Question	On the dominator tree
Which vertices become unreachable if $v$ fails?	$v$’s subtree
How many vertices depend on $v$?	subtree size
Is $u$ required to reach $v$?	is $u$ an ancestor of $v$
Critical single points of failure	vertices with large subtrees
Vertices reachable only through $v$	subtree minus $v$

Where it comes from

Dominators were invented for compilers. In SSA (static single assignment) construction, a $\varphi$-function for variable $x$ is needed exactly at the dominance frontier of $x$‘s definitions. Loop detection, code motion, and control dependence all use the dominator tree. Every optimising compiler computes one.

Post-dominators

Run the same algorithm on the reversed graph from the exit vertex. $u$ post-dominates $v$ if every path from $v$ to the exit passes through $u$. The combination of dominators and post-dominators gives control dependence, which is what tells a compiler which statements are conditionally executed.

See also: Lengauer-Tarjan · LCA · SCC