Tech Notes: Computing graph dominators
Computing graph dominators
August 13, 2026
A few years back I wrote about the dominator tree of a dependency graph,<br>which is one of my favorite tricks for thinking about dependencies. It turns out<br>a new tinkering project of mine again needs a dominator tree, so I invested some<br>time to deepen my understanding.
In this post I present an algorithm for computing graph dominators along with<br>the intuition behind it.
Definitions
There are two central definitions that I will handwave some details about; you<br>can read Wikipedia for<br>those. Here's a graph to visualize them. Hover some nodes while you read.
Node x dominates node y if all paths from the graph's root (a, in this<br>example) to y must go through x. If you hover a node here, its dominators are<br>shown in yellow.
Node x immediately dominates y if it is the lowest dominator above y. The<br>immediate dominator of the hovered node is shown with a thicker outline.
Again, see my earlier post for some other framings of what these mean or<br>how to think about them.
Choosing an algorithm
There is a continuous stream of research going back to 1959 publishing different<br>algorithms for computing dominators with varying levels of implementation<br>complexity. Lengauer-Tarjan ("LT") from 1979 seems to be the standard but it is<br>relatively complex, involving spanning trees and union find.
In LLVM, i.e. in a tool where performance really does matter, it appears they<br>use LT but have changed their implementation over time. For example<br>in this work in 2017 they<br>mention in a large compile they were computing 6.5 million dominator trees(!)<br>and they changed to an approach that supports incremental updates.
The paper "A Simple, Fast Dominance Algorithm" from 2001 describes a simple<br>algorithm that they claim is both useful for learning and in practice about 2.5x<br>faster than LT.
The later paper "Finding Dominators in Practice" compares multiple algorithms,<br>and regarding the above claim they write: "a more careful implementation of<br>[Lengauer-Tarjan] later led to different results (personal communication)",<br>which is not a great sign. However, in that paper they also gather numbers<br>comparing five different algorithms across a collection of graphs and find that<br>they all land somewhere between 2-5x the time of a breadth-first search, which<br>itself they measure in microseconds. Which is to say, for the kinds of graphs<br>that you or I likely care about, the difference doesn't matter.
If you like reading papers (I do! it's a worthy habit to develop!), you're best<br>off reading "A Simple, Fast Dominance Algorithm" directly. But in part for<br>deepening my own understanding by saying it in my own words, the rest of this<br>post will dive into the "Simple, Fast" algorithm.
The approach
Their presentation is roughly two parts. First, they describe a general approach<br>for computing dominators and why it works. Second, they show an algorithm that<br>uses some representation tricks to implement that approach efficiently.
The general approach is describing the computation as a data-flow equation,<br>which defines a per-node computation that recursively depends on itself.
Define dom[n] as the set of dominators for node n. Then the data flow<br>equation is:
dom[root] = {root}<br>dom[n] = intersect(dom[p] for p in predecessors(n)) union {n}
In words, the dominator set of a node is the intersection of the dominators of<br>the node's predecessors, as well as the node itself. (To make sense of this,<br>don't overlook that dom[n] always includes n!)
To compute this, you run in a loop that updates each node until the output stops<br>changing.
changed = True<br>while changed:<br>changed = False<br>for n in nodes:<br>new = recompute(n)<br>if new != dom[n]<br>dom[n] = new<br>changed = True
In the paper, they connect this to other research that shows this will converge<br>on the correct answer in a relatively small number of iterations — if you<br>iterate the nodes in reverse postorder, more on that in a moment. For our<br>purposes of intuition, I think it's enough to say "this is guaranteed to<br>converge on the correct result fast enough, see the paper for proof".
Why does this work? In the above sample graph, try hovering the predecessors of<br>node g or h and mentally intersect the sets in yellow to see it produce<br>their own yellow sets. Intuitively the sets represent something like a path from<br>the root (though they may not be a full path; witness the dominator set for<br>g), and intersecting the sets results in the nodes found on all paths from the<br>root.
As given this is inefficient to compute — though I suspect if you're writing<br>Python or whatever and working with a small graph it's probably fine. The actual<br>algorithm from the paper is more efficient.
Traversal order
To get to the algorithm we first must detour into graph traversal, as it relies<br>on a reverse postorder traversal of the graph.
A preorder traversal visits a node then its children; a postorder visits the<br>children before the node, recursively; a reverse...