도미네이터 트리

흐름 그래프에서 "반드시 거치는" 정점

시작점 \(s\)가 있는 유향 그래프(흐름 그래프)에서, 정점 \(w\)를 지배(dominate) 하는 정점 \(v\)란:

\(s\)에서 \(w\)로 가는 모든 경로가 \(v\)를 지난다.

\(w\) 자신과 \(s\)는 항상 \(w\)를 지배한다. \(w\)의 지배자 중 \(w\)가 아니면서 가장 가까운(다른 모든 지배자에게 지배되는) 것이 즉시 지배자(immediate dominator) \(\text{idom}(w)\)다.

도미네이터 트리

각 정점 \(w \neq s\)를 그 부모 \(\text{idom}(w)\)에 연결하면 \(s\)를 루트로 하는 트리가 된다. 이것이 도미네이터 트리다. 핵심 성질:

\(v\)가 \(w\)를 지배할 필요충분조건은, 도미네이터 트리에서 \(v\)가 \(w\)의 조상인 것.

즉 "지배 = 트리 조상 관계"로 압축된다. 컴파일러 최적화(SSA, 루프 분석), 회로 분석, 그래프 신뢰성에서 핵심 자료구조다.

즉시 지배자의 유일성

\(\text{idom}(w)\)가 유일하다는 것은 비자명하다. \(w\)를 지배하는 정점들 \(D(w) \setminus \{w\}\)가 전순서 를 이룬다는 보조정리에서 따른다: \(a, b\)가 모두 \(w\)를 지배하면, \(s \to w\) 경로 위에서 \(a\)가 먼저 나오거나 \(b\)가 먼저 나오므로 둘 중 하나가 다른 하나를 지배한다. 따라서 가장 가까운 지배자가 유일하게 결정된다.

단순 알고리즘: 정점 제거 테스트

각 정점 \(v\)를 지우고 \(s\)에서 BFS/DFS로 도달 가능성을 본다. \(v\) 제거로 도달 불가능해진 정점들이 \(v\)에 지배된다. \(O(V \cdot E)\). 작은 그래프엔 충분하지만, 큰 그래프엔 느리다.

Lengauer–Tarjan: \(O(E \alpha(V))\)

표준 고속 알고리즘. 골자:

1. \(s\)에서 DFS, DFS 번호(dfn) 부여.
2. 각 정점 \(w\)의 semi-dominator \(\text{sdom}(w)\) 계산:
   $$ \text{sdom}(w) = \min\{\,\text{dfn}(v) : (v, \dots, w)\text{ 경로의 내부 정점이 모두 dfn} > \text{dfn}(w)\,\}. $$
   직관적으로 "DFS 트리 바깥의 더 일찍 발견된 정점에서 들어오는 최소 진입점".
3. semi-dom으로부터 idom을 보정(두 경우의 규칙).

semi-dom 계산과 idom 보정 모두 link-eval (경로 압축이 있는 union-find 변형)으로 처리해 거의 선형이다.

semi → idom 보정 규칙

DFS 트리 경로 \(\text{sdom}(w) \to w\) 에서 sdom이 최소인 정점을 \(u\)라 하면:

$$ \text{idom}(w) = \begin{cases} \text{sdom}(w), & \text{sdom}(u) = \text{sdom}(w) \\ \text{idom}(u), & \text{그 외 (지연 결정)}.\end{cases} $$

지연된 경우는 dfn 역순으로 한 번 더 훑어 확정한다.

정리

• 지배 = 도미네이터 트리의 조상 관계.
• idom 유일성은 지배자 전순서에서.
• Lengauer–Tarjan으로 거의 선형. 다음 강의에서 구현.

자료구조

int n, dfn[N], rev[N], par[N], cnt;     // dfn: DFS 번호, rev: 번호→정점
int semi[N], idom[N], best[N], anc[N];  // link-eval용
vector<int> g[N], rg[N], bucket[N];     // 정방향, 역방향, sdom 버킷

1) DFS 번호 매기기

void dfs(int u) {
    dfn[u] = ++cnt; rev[cnt] = u;
    semi[u] = dfn[u]; best[u] = u; anc[u] = 0;
    for (int v : g[u]) if (!dfn[v]) {
        par[v] = u;   // DFS 트리 부모
        dfs(v);
    }
}

2) link-eval (경로 압축 union-find 변형)

eval(v)는 \(v\)의 조상 중 semi가 최소인 정점을 반환한다.

int eval(int v) {
    if (anc[v] == 0) return best[v];
    compress(v);
    return best[v];
}
void compress(int v) {
    int a = anc[v];
    if (anc[a] == 0) return;
    compress(a);
    if (semi[best[a]] < semi[best[v]]) best[v] = best[a];
    anc[v] = anc[a];
}
void link(int v, int w) { anc[w] = v; }   // w의 부모를 v로

3) semi-dom 계산 + idom 1차

dfn 역순으로 처리한다.

void build(int root) {
    cnt = 0;
    dfs(root);
    for (int i = cnt; i >= 2; i--) {
        int w = rev[i];
        for (int v : rg[w]) {             // w로 들어오는 간선
            if (!dfn[v]) continue;        // 도달 불가능 정점 무시
            int u = eval(v);
            if (semi[u] < semi[w]) semi[w] = semi[u];
        }
        bucket[rev[semi[w]]].push_back(w);
        link(par[w], w);
        // par[w]의 버킷 처리
        for (int v : bucket[par[w]]) {
            int u = eval(v);
            idom[v] = (semi[u] < semi[v]) ? u : par[w];
        }
        bucket[par[w]].clear();
    }
}

4) idom 확정 (정방향 보정)

void finalize() {
    for (int i = 2; i <= cnt; i++) {
        int w = rev[i];
        if (idom[w] != rev[semi[w]])      // 지연된 경우
            idom[w] = idom[idom[w]];
    }
    idom[rev[1]] = 0;                     // 루트는 부모 없음
}

이후 idom[w]가 도미네이터 트리의 부모다. 트리를 세우면 조상 질의(LCA, 서브트리)로 지배 관계를 \(O(\log n)\) 또는 \(O(1)\)에 답할 수 있다.

활용 예제

• 간선 하나가 끊겼을 때 도달 불가능해지는 정점 수: 끊는 간선이 도미네이터 트리에서 어떤 서브트리를 떼어내는지로 계산.
• 모든 경로가 거쳐야 하는 관문(병목) 찾기: \(t\)를 도착점으로 두고 도미네이터 트리에서 \(s \to t\) 경로 위 정점들.
• 신뢰성/SPOF 분석: 단일 장애점 = \(t\)의 비자명한 지배자.

// 도미네이터 트리에서 정점 v를 지우면 도달 불가능해지는 정점 수
// = v를 루트로 하는 서브트리 크기 (도달 가능한 것만)

함정

• 도달 불가능한 정점은 dfn이 0; 모든 단계에서 건너뛴다.
• 역방향 그래프 rg를 잊지 말 것(semi-dom은 진입 간선으로 계산).
• DFS 재귀 깊이 한계(큰 그래프는 명시적 스택).

복잡도는 \(O(E\,\alpha(V))\)로 사실상 선형. \(V, E \le 2 \times 10^5\)급도 가볍게 통과한다.