木構造と動的計画法の親和性

木（Tree）は再帰的に定義されるデータ構造であり、部分問題に分割して解く動的計画法（DP）と非常に相性が良いです。本稿では、木構造におけるDPの典型的な問題と、その状態遷移および実装について解説します。

グラフ理論における4つの典型問題

一般のグラフにおいて、以下の4つの問題はNP困難またはco-NP完全として知られていますが、木構造や二部グラフといった特殊な条件下では多項式時間で解くことが可能です。

1. 最大独立集合 (Maximum Independent Set)

問題定義: グラフ \(G\) から、互いに隣接しない（辺で結ばれていない）頂点の部分集合 \(V'\) を選び、そのサイズ（または重みの和）を最大化します。

状態定義: state[node][0/1] を、頂点 node を「選ばない(0) / 選ぶ(1)」場合の最大値とします。

遷移式:

• state[node][1] = weight[node] + Σ state[child][0]
• state[node][0] = Σ max(state[child][0], state[child][1])

void computeIndependentSet(int curr, int parent) {
    state[curr][0] = 0;
    state[curr][1] = nodeWeight[curr];
    
    for (int nextNode : graph[curr]) {
        if (nextNode == parent) continue;
        computeIndependentSet(nextNode, curr);
        state[curr][0] += std::max(state[nextNode][0], state[nextNode][1]);
        state[curr][1] += state[nextNode][0];
    }
}

2. 最小支配集合 (Minimum Dominating Set)

問題定義: グラフ \(G\) のすべての頂点が、選ばれた頂点集合 \(V'\) のいずれかと隣接するか、あるいは \(V'\) に含まれるようにし、\(V'\) のサイズを最小化します。

状態定義:

• state[node][0]: 頂点 node 自身が選ばれ、自身をカバーする。
• state[node][1]: 頂点 node は選ばれておらず、いずれかの子ノードによってカバーされる。
• state[node][2]: 頂点 node は選ばれておらず、親ノードによってカバーされる。

遷移式:

• state[node][0] = 1 + Σ min(state[child][0], state[child][1], state[child][2])
• state[node][2] = Σ min(state[child][0], state[child][1])
• state[node][1] = state[node][2] + min_{child} (state[child][0] - min(state[child][0], state[child][1])) ※少なくとも1つの子が自身を選んでいる必要があるため、差分の最小値を加算します。

void computeDominatingSet(int curr, int parent) {
    state[curr][0] = 1;
    state[curr][2] = 0;
    
    for (int child : graph[curr]) {
        if (child == parent) continue;
        computeDominatingSet(child, curr);
        state[curr][0] += std::min({state[child][0], state[child][1], state[child][2]});
        state[curr][2] += std::min(state[child][0], state[child][1]);
    }

    int minDiff = INF;
    for (int child : graph[curr]) {
        if (child == parent) continue;
        int diff = state[child][0] - std::min(state[child][0], state[child][1]);
        minDiff = std::min(minDiff, diff);
    }
    state[curr][1] = state[curr][2] + minDiff;
}

※根ノードには親が存在しないため、最終的な答えは min(state[root][0], state[root][1]) となります。

3. 最小頂点被覆 (Minimum Vertex Cover)

問題定義: グラフ \(G\) のすべての辺について、その両端点の少なくとも一方が頂点集合 \(V'\) に含まれるようにし、\(V'\) のサイズを最小化します。

これは最大独立集合の補集合を求める問題と等価であり、状態遷移も似ています。

void computeVertexCover(int curr, int parent) {
    state[curr][0] = 0; // 選ばない場合、子は必ず選ばなければならない
    state[curr][1] = 1; // 選ぶ場合
    
    for (int child : graph[curr]) {
        if (child == parent) continue;
        computeVertexCover(child, curr);
        state[curr][0] += state[child][1];
        state[curr][1] += std::min(state[child][0], state[child][1]);
    }
}

4. 最大マッチング (Maximum Matching)

問題定義: グラフ \(G\) から、互いに端点を共有しない辺の集合 \(E'\) を選び、そのサイズを最大化します。

状態の持ち方は最小支配集合と類似したアプローチが取れます。

状態定義:

• state[node][0]: 頂点 node がどのマッチング辺の端点にもなっていない。
• state[node][1]: 頂点 node がいずれかの子との間の辺でマッチングに含まれている。

void computeMaxMatching(int curr, int parent) {
    state[curr][0] = 0;
    
    for (int child : graph[curr]) {
        if (child == parent) continue;
        computeMaxMatching(child, curr);
        state[curr][0] += std::max(state[child][0], state[child][1]);
    }

    int maxGain = -INF;
    for (int child : graph[curr]) {
        if (child == parent) continue;
        // 子childと辺を結ぶ場合のゲインを計算
        int gain = state[child][0] + 1 - std::max(state[child][0], state[child][1]);
        maxGain = std::max(maxGain, gain);
    }
    state[curr][1] = state[curr][0] + maxGain;
}

木の直径 (Diameter of a Tree)

木の直径とは、木に含まれるパスの中で最も長いものの長さを指します。これには主に2つのアプローチがあります。

アプローチ1: 2回の探索 (DFS/BFS)

任意の頂点 \(u\) から最も遠い頂点 \(s\) を求め、次に \(s\) から最も遠い頂点 \(t\) を求めます。このとき、パス \(s \to t\) が木の直径となります。

証明の概要:
もし \(s\) から最も遠い点 \(T\) が直径の端点でないと仮定すると、距離の三角不等式や木のパスの一意性から矛盾が生じます。したがって、任意の点から最も遠い点は必ず直径の端点のいずれかになります。

アプローチ2: 動的計画法

各頂点 \(u\) において、その部分木内での「最長パス」と「2番目に長いパス」を管理します。直径は、ある頂点 \(u\) を中継点とした場合の「最長パス + 2番目に長いパス」の最大値となります。

longestPath[node] を頂点 node を始点とする最長パスの長さとします。

int treeDiameter = 0;

void computeDiameter(int curr, int parent) {
    int longest = 0;
    int secondLongest = 0;

    for (int child : graph[curr]) {
        if (child == parent) continue;
        computeDiameter(child, curr);
        
        int pathLength = longestPath[child] + edgeWeight[curr][child];
        
        if (pathLength > longest) {
            secondLongest = longest;
            longest = pathLength;
        } else if (pathLength > secondLongest) {
            secondLongest = pathLength;
        }
    }
    
    longestPath[curr] = longest;
    treeDiameter = std::max(treeDiameter, longest + secondLongest);
}