二分探索を用いてグラフの最小頂点被覆のサイズを求めるC++プログラム

本記事では、二分探索（バイナリサーチ）を活用して、与えられたグラフの最小頂点被覆のサイズを求めるC++プログラムについて解説します。

最小頂点被覆とは？

最小頂点被覆（Minimum Vertex Cover）とは、グラフのすべての辺が、集合内のいずれかの頂点に接続（インシデント）するような頂点集合のうち、頂点数が最小のものを指します。

例として、以下のグラフを見てみましょう。

2 ---- 4 ---- 6
|      |
|      |
|      |
3 ---- 5

このグラフの場合、最小頂点被覆は「頂点3」と「頂点4」の2つの頂点から構成されます。グラフ上のすべての辺は、必ず頂点3または頂点4のいずれかに接続しているためです。

アルゴリズムの流れ

このプログラムでは、次の手順で最小頂点被覆のサイズを求めます。

1. 頂点被覆の候補サイズ k を二分探索で決定します。
2. ビット演算を用いて、k 個の頂点を選ぶすべての組み合わせを効率的に列挙します。
3. 選択した頂点集合が、グラフのすべての辺を被覆できるかを判定します。
4. 被覆が成立する最小の k を二分探索によって絞り込み、結果として返します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
#define max 15
// グラフを格納する配列
bool arr[max][max];
// サイズ k の頂点被覆が存在するかを判定する関数
bool check_cover(int V, int k, int E) {
    int set = (1 << k) - 1;
    int limit = (1 << V);
    // 辺の訪問状態を記録する配列
    bool vis[max][max];
    while (set < limit) {
        // 各反復のたびに訪問状態をリセット
        memset(vis, 0, sizeof vis);
        int count = 0;
        // ビットが立っている頂点を確認
        for (int j = 1, v = 1 ; j < limit ; j = j << 1, v++) {
            if (set & j) {
                // 辺を訪問済みとしてマーク
                for (int k = 1 ; k <= V ; k++) {
                    if (arr[v][k] && !vis[v][k]) {
                        vis[v][k] = 1;
                        vis[k][v] = 1;
                        count++;
                    }
                }
            }
        }
        // すべての辺が被覆できた場合
        if (count == E)
            return true;
        // 次の組み合わせを生成（Gosper's Hack）
        int c = set & -set;
        int r = set + c;
        set = (((r^set) >> 2) / c) | r;
    }
    return false;
}
// 最小頂点被覆を求める関数
int find_cover(int n, int m) {
    // 二分探索を実行
    int left = 1, right = n;
    while (right > left){
        int mid = (left + right) >> 1;
        if (check_cover(n, mid, m) == false)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}
// グラフに辺を追加する関数
void add_edge(int u, int v) {
    arr[u][v] = 1;
    arr[v][u] = 1;
}
int main() {
    memset(arr, 0, sizeof arr);
    int V = 6, E = 5;
    add_edge(2, 3);
    add_edge(2, 4);
    add_edge(3, 5);
    add_edge(4, 5);
    add_edge(4, 6);
    cout << "Size of Minimum Vertex Cover : " << find_cover(V, E) << endl;
    return 0;
}

実行結果

Size of Minimum Vertex Cover : 2

頂点数6・辺数5のグラフに対して、最小頂点被覆のサイズとして「2」が出力されます。これは、頂点3と頂点4を選ぶことで、すべての辺を被覆できることを意味します。

なお、この手法は組み合わせの全列挙を伴うため、頂点数が多いグラフでは計算量が急増します。小規模なグラフ向けの実装である点に注意してください。