To understand dominator trees, we first define the concept of dominance within a directed graph containing a designated entry node \(s\). For any two nodes \(u\) and \(v\), if every possible path from \(s\) to \(u\) must traverse \(v\), then \(v\) is considered a dominator of \(u\). Alternatively, this implies that removing \(v\) breaks connectivity between \(s\) and \(u\). The collection of all such dominators constitutes the dominator set for \(u\).

A fundamental property of this relationship is transitivity within pairs. If both \(x\) and \(y\) dominate a target node \(z\), there exists a strict dominance relation between \(x\) and \(y\); one must dominate the other. Consequently, these relations form a tree structure known as the Dominator Tree. In this tree, the parent of a node \(u\) is defined as its Immediate Dominator—the specific dominator closest to \(u\) in terms of distance.

Construction on Directed Acyclic Graphs (DAG)

When working with a DAG, constructing the tree is straightforward using topological sorting. For a node \(x\), let its direct predecessors be \(y_1, y_2, \dots\). To dominate \(x\), a node must dominate all \(y_i\) simultaneously. Therefore, the Immediate Dominator for \(x\) corresponds to the Lowest Common Ancestor (LCA) of the Immediate Dominators of its predecessors in the constructed tree.

We process nodes in topological order to ensure dependencies are resolved before computing current values. Since the tree grows dynamically, LCA queries can be handled efficiently using Binary Lifting combined with depth tracking.

void process_dag(graph &g) {
    int root = g.start_node;
    vector<int> q;
    // Initialize topological queue
    for (int i = 0; i < g.node_count; ++i) 
        if (g.in_degree[i] == 0 && i != root) continue; // Handle start node logic specifically
    
    q.push_back(root);
    
    // Standard Topological Sort Loop
    int head = 0;
    while(head < q.size()){
        int u = q[head++];
        
        // Calculate LCA of all predecessor dominators
        int idom = -1;
        for (int v : g.predecessors(u)) {
            if (idom == -1) idom = immediate_dom[v];
            else idom = get_lca(idom, immediate_dom[v]);
        }

        immediate_dom[u] = idom;
        if (idom != -1) depth[u] = depth[idom] + 1;

        // Setup Binary Lifting Table
        up_table[u][0] = idom;
        for (int j = 1; j < LOG_LEVEL; ++j) {
            up_table[u][j] = up_table[up_table[u][j-1]][j-1];
        }

        // Push successors to queue
        for (int v : g.successors(u)) {
            if (--g.in_degree[v] == 0) {
                q.push_back(v);
            }
        }
    }
}

General Directed Graphs

For general graphs, a brute-force removal of nodes results in \(O(n^2)\) complexity per query, which is inefficient. The standard optimization involves deriving a Depth First Search (DFS) spanning tree. Within this tree, the dominators of any node \(u\) must lie on the path from the root to \(u\).

The core concept here is the Semi-Dominator (\(semi_u\)). This is defined as the ancestor of \(u\) with the minimum DFS discovery time that can reach \(u\) via a path where all intermediate nodes have a higher discovery time than \(u\).

This allows us too transform the problem back into a DAG structure: by linking \(semi_u\) directly to \(u\), we simplify the dependency graph. Finding \(semi_u\) efficiently requires processing vertices in reverse DFS order. We utilize a Disjoint Set Union (DSU) structure to maintain the minimum discovery time encountered so far in the partial tree traversal.

int min_semi(int x) {
    if (dsu_parent[x] != x) {
        int root = min_semi(dsu_parent[x]);
        // Path compression updates the minimum value found
        dsu_min_val[x] = min(dsu_min_val[x], dsu_min_val[dsu_parent[x]]);
        dsu_parent[x] = root;
    }
    return dsu_parent[x];
}

// Initialization
for (int i = 1; i <= n; ++i) {
    dsu_parent[i] = i;
    dsu_min_val[i] = dfs_time[i];
}

// Process in reverse DFS order
for (int i = n; i >= 1; --i) {
    int u = nodes_by_dfs[i];
    
    // Check incoming edges
    for (int v : reverse_adj[u]) {
        min_semi(v); // Compress and find representative
        // Update candidate semi-dom based on min valuation
        dsu_min_val[u] = min(dsu_min_val[u], dsu_min_val[v]);
    }
    
    // Link u to its calculated semi-dom
    semi_dom[u] = nodes_by_dfs[dsu_min_val[u]];
    
    // Union u with its parent in DFS tree
    dsu_parent[u] = dfs_parent[u];
}

Note that in this reduced dependency graph, the number of edges scales linearly, allowing subsequent dominator calculation steps to run efficiently.

Dynamic Modification Analysis

Consider a scenario where we need to evaluate the impact of inserting a single new directed edge into the graph. Specifically, how does this affect the count of nodes whose dominance relationships change?

If an edge \(x \rightarrow y\) is added, the immediate dominator of \(y\) in the original tree might no longer be valid. Since adding an edge reduces constraints, the set of dominators can shrink. We can determine if the Immediate Dominator of \(y\) remains valid by verifying reachability. Specifically, we check if the previous parent of \(y\) still dominates \(y\) given the new connection.

If the dominance status changes, this ripple effect propagates downwards through \(y\)'s entire subtree in the dominator tree, altering their status as well. Thus, we only need to verify the condition at \(y\) and multiply by the size of its subtree if a change occurs.