頂点被覆問題を二分木で解く！動的計画法によるアルゴリズムとC++実装

頂点被覆問題とは

無向グラフにおける頂点被覆（Vertex Cover）とは、グラフのすべての辺 (u, v) に対して、u または v の少なくとも一方が必ずその集合に含まれるような頂点の部分集合のことを指します。

二分木を利用することで、頂点被覆問題を動的計画法によって効率的に解くことができます。

解法の考え方

この問題は、根（ルート）ノードに着目して、次の2つの場合に分割して考えることができます。

ケース1：根を頂点被覆に含める場合

根が頂点被覆に含まれると、根から子へ伸びるすべての辺が自動的に覆われます。したがって、左部分木と右部分木それぞれの最小頂点被覆サイズを求め、根自身の分として「1」を加算すればよいのです。

ケース2：根を頂点被覆に含めない場合

根を含めない場合は、根と直接つながっている子ノードを必ず被覆に含める必要があります。そこで、左の子と右の子を被覆に加え、さらにそれらの子の部分木についても同様に再帰的に計算を行います。

最終的な答えは、これら2つのケースのうち小さい方の値となります。

入力と出力

入力：二分木
出力：頂点被覆のサイズは 3

アルゴリズム

この問題では、各ノードが「データ」と「そのノードが覆う頂点数（vCover）」を保持する二分木を構築します。

入力：二分木の根ノード

出力：根が覆う頂点の数

vertexCover(root node)
Begin
    if root is φ, then
        return 0
    if root has no child, then
        return 0
    if vCover(root) ≠ 0, then
        return vCover(root)　// 計算済みなら保存値を返す（メモ化）
    withRoot := 1 + vertexCover(left(root)) + vertexCover(right(root))
    withoutRoot := 0

    if root has left child, then
        withoutRoot := withoutRoot + 1 + vertexCover(left(left(root))) + vertexCover(left(right(root)))
    if root has right child, then
        withoutRoot := withoutRoot + 1 + vertexCover(right(left(root))) + vertexCover(right(right(root)))
    vCover(root) := min(withRoot, withoutRoot)
    return vCover(root)
End

処理のポイント

• 木が空、または葉ノードの場合は 0 を返す（覆うべき辺が存在しないため）
• 一度計算したノードの結果は保存し、再利用する（メモ化による高速化）
• 根を含む場合と含まない場合の両方を計算し、小さい方を採用する

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int data;
    int vCover;
    node *left, *right;
};

node *getNode(int data) {
    node *newNode = new (node);
    newNode->data = data;
    newNode->vCover = 0; // 頂点被覆を0で初期化
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;      // 新しく作成したノード
}

int vertexCover(node *root) {
    if(root == NULL)     // 木が空の場合
        return 0;
    if(root->left == NULL && root->right == NULL)   // 根から他の辺がない場合
        return 0;

    if(root->vCover != 0)   // すでに計算済みの場合はその値を返す
        return root->vCover;

    int sizeWithRoot = 1 + vertexCover(root->left) + vertexCover(root->right);
    int sizeWithOutRoot = 0;

    if(root->left != NULL)   // 根を含めず、左の子を採用する場合
        sizeWithOutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
    if(root->right != NULL)  // 根を含めず、右の子を採用する場合
        sizeWithOutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);

    root->vCover = (sizeWithRoot < sizeWithOutRoot)?sizeWithRoot:sizeWithOutRoot; // 最小頂点被覆
    return root->vCover;
}

int main() {
    // 頂点被覆を確認するための木を作成
    node *root = getNode(20);
    root->left = getNode(8); root->right = getNode(22);
    root->left->left = getNode(4); root->left->right = getNode(12);
    root->left->right->left = getNode(10); root->left->right->right = getNode(14);
    root->right->right = getNode(25);
    cout << "Minimal vertex cover: " << vertexCover(root);
}

実行結果

Minimal vertex cover: 3

まとめ

頂点被覆問題は一般のグラフではNP困難な問題ですが、木構造に限定すれば、動的計画法とメモ化を組み合わせることで各ノードを一度だけ処理し、線形時間 O(n) で解くことができます。「自分を含めるか、子を含めるか」という2択を各ノードで比較し、小さい方を選ぶというシンプルな戦略がこのアルゴリズムの鍵となります。