5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ True. For a DAG, dominators could be computed with a single pass using the definition. Currently I am using union-find with this to get the dominator tree in a single iteration. I was wondering if that's the best we can do. $\endgroup$ – Saswat Padhi May 31 '15 at 7:48
  • 1
    $\begingroup$ Well, we certainly can't do better than a single iteration over all nodes! The reason why I suggested topological sort is it's possible that you already have a topological ordering for some reason. Union-find also works, and possibly even works better. $\endgroup$ – Pseudonym Jun 2 '15 at 1:05
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In step 3, I think it'd be clearer to use topological order, not DFS. DFS doesn't have the property that "no vertex is visited before all its ancestors". It's not entirely clear what is meant by "Enter $v$ only if..." -- I presume you are modifying DFS in some way, but the exact details are the modification are unclear, and at that point it's not DFS any longer but something else. $\endgroup$ – D.W. Jan 14 '17 at 17:21
  • $\begingroup$ Can you justify the claimed running time for LCA? Standard LCA algorithms work in a batch mode: you do preprocessing once (the entire tree must be known in advance), then a bunch of queries (the tree isn't allowed to change as you go). In this algorithm the tree is changing as you go, so you need some kind of dynamic LCA data structure. Can that be done? Do you have a link or reference for how to do that? $\endgroup$ – D.W. Jan 14 '17 at 17:23
  • $\begingroup$ About Comment 1: Most DFS algorithms are modifications of the original DFS. That's simple! The DFS of Step 3 has just one more aditional check to call the recursive function, i.e., to visit $v$. To understand it better, just check this line of my implementation: github.com/matheuscscp/problem-solving/blob/master/lib/graphs/… $\endgroup$ – matheuscscp Jan 14 '17 at 23:11
  • $\begingroup$ About Comment 2: I proposed the dynamic programming version of LCA. All dynamic programming algorithms can be implemented in a bottom-up fashion (where the answer for all DP-states are computed at once), or in a top-down fashion. The latter is done with a recursive function that just returns the answer for the required state, if it's already stored in the memoization table (and compute the answer otherwise). This is a lazy computation! You'll only compute the answer for a state when necessary! Both implementations have the same running time, though. $\endgroup$ – matheuscscp Jan 14 '17 at 23:20
  • $\begingroup$ If it's not clear yet, the algorithm works with a lazy evaluation of the LCA dynamic programming states. Each time Step 3.1 runs, the $O(\lg |V|)$ LCA query algorithm will require some states of the LCA dynamic programming. They'll be correctly calculated (if they're not calculated yet), because the required parts of the dominator tree are already in their final state, due to topological order enforced by Step 3.2. The edges currently being updated are never required! $\endgroup$ – matheuscscp Jan 14 '17 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.