Dominator Tree for DAG

Question

Is there a fast algorithm to compute dominator tree for acyclic graphs?

The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?

Answer 1

Recall the definition of dominators:

$$\hbox{Dom}(n_o) = \{ n_o \}$$ $$\hbox{Dom}(n) = \{ n \} \cup \bigcap_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$

This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.

It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.

Answer 2

In a directed acyclic graph $D = (V,E)$, the dominator tree $T(s) = (V(s),E(s))$ with respect to source vertex $s \in V$ is such that $V(s) \subseteq V$ is the subset of vertices reachable from $s$ and $$E(s) = \{(\text{idom}(u,s),u) \mid u \in V(s) - \{s\}\}$$ where $\text{idom}(u,s)$ denotes the immediate dominator of $u$ regarding $s$ (closest vertex to $u$ present in all paths from $s$ to $u$). Hence, $\text{idom}(u,s)$ is defined only if $u \in V(s)$. Also, we define $\text{idom}(s,s) = s$, despite $(\text{idom}(s,s),s) \notin E(s)$.

Now, let's fix $s$ and write $\text{idom}(u) = \text{idom}(u,s)$. Also, let's write as $\text{deg}^-(u)$ the indegree of $u \in V(s)$, excluding external edges (any edge $(v,u)$ such that $v \notin V(s)$ is not considered).

Follows by induction that $$\text{idom}(u) = \text{lca} \{v \mid v \in V(s) \wedge (v,u) \in E\}$$ where $\text{lca}(W)$ denotes the lowest common ancestor of all vertices in $W$, if $W$ is a subset of vertices of a tree. In this case, the dominator tree.

Algorithm:

1. Initialize $\text{idom}(u) \gets u$ for all $u \in V(s)$.
2. Run a depth-first search from $s$ to compute $\deg^-(u)$ for all $u \in V(s)$.

3. Run a recursive "DFS-like-but-not-depth-first" search starting from $s$. For each edge $(u,v)$ discovered in this search:

   3.1. If $\text{idom}(v) = v$, then $\text{idom}(v) \gets u$, else $\text{idom}(v) \gets \text{lca}\{\text{idom}(v),u\}$.

   3.2. Decrease $\deg^-(v)$ by one. Enter $v$ recursively only if $\deg^-(v)$ becomes zero!

The algorithm is correct because, since $D$ is a DAG, Step 3.2 ensures topological order. Hence, the LCA query of Step 3.1 always runs correctly, as the dominator tree edges for all vertices $x \in V(s)$ that reach $u$ are already built (this is induction).

Steps 1 and 2 cost $O(|V|+|E|)$ time and $O(|V|)$ space.

LCA preprocessing for Step 3 costs $O(|E| + |V| \lg |V|)$ time and $O(|V| \lg |V|)$ space. Each LCA query costs $O(\lg |V|)$ time, so Step 3 costs $O(|V| + |E| \lg |V|)$ time.

The overall costs are $O((|V|+|E|) \lg |V|)$ time and $O(|V| \lg |V|)$ space.

LCA preprocessing can actually be made on the fly with the help of dynamic programming and memoization! The time cost will be the same, but amortized.

I saw this algorithm here. The dominator tree was built over the Dijkstra's shortest paths DAG.

Here is my C++ 14 implementation.