C++でグラフの頂点被覆を求めるヒューリスティックを実装する方法

頂点被覆（Vertex Cover）とは？

グラフの頂点被覆（Vertex Cover）とは、グラフ内のすべての辺について、その辺が結ぶ2つの頂点MとNのうち、少なくとも一方（または両方）が集合Vに含まれるような頂点集合Vのことです。

頂点被覆を求める問題はNP困難として知られており、大規模なグラフに対して厳密な最適解を多項式時間で求めることは一般的に困難です。そこで本記事では、近似解を高速に得られる貪欲法ベースのヒューリスティックをC++で実装します。

アルゴリズムの手順

このヒューリスティックは、「辺を1つ選び、その両端の頂点を解に加え、それらに関連する辺を取り除く」という操作を繰り返すシンプルな貪欲法です。

1. 集合Sを空として初期化します。
2. グラフから1つの辺Eを選びます。その端点をM、Nとします。
3. 両方の頂点MとNを集合Sに追加します。
4. MまたはNを端点とするすべての辺をグラフから取り除きます。
5. グラフにまだ辺が残っている場合は、手順2に戻ります。
6. 最終的な集合Sを出力します。これがグラフの頂点被覆となります。

C++による実装例

以下は、上記のヒューリスティックを実装したC++プログラムです。グラフを隣接リストで構築し、どちらの端点もまだ選ばれていない辺が見つかるたびに、両端の頂点を解としてマークしていきます。

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
bool v[11110];
int i,j;
vector<int> sol_vertex(int n,int e) {
    vector<int> S;
    for(i=0;i<n;i++) {
        if(!v[i]) {
            for(j=0;j<(int)g[i].size();j++) {
                if(!v[g[i][j]]) {
                    v[i]=true;
                    v[g[i][j]]=true;
                    break;
                }
            }
        }
    }
    for(i=0;i<n;i++)
        if(v[i])
        S.push_back(i);
    return S;
}
int main() {
    int n,e,a,b;
    cout<<"Enter number of vertices:";
    cin>>n;
    cout<<"Enter number of Edges:";
    cin>>e;
    g.resize(n);
    memset(v,0,sizeof(v));
    for(i=0;i<e;i++) {
        cout<<"Enter the end-points of edge "<<i+1<<" : ";
        cin>>a>>b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> S = sol_vertex(n,e);
    cout<<"The required vertex cover is as follows:
";
    for(i=0;i<(int)S.size();i++)
        cout<<S[i]+1<<" ";
    return 0;
}

出力結果

たとえば、頂点4個・辺5本のグラフに対して次のように入力すると、プログラムは以下の出力を返します。

Enter number of vertices:4
Enter number of Edges:5
Enter the end-points of edge 1 : 2 1
Enter the end-points of edge 2 : 3 2
Enter the end-points of edge 3 : 4 3
Enter the end-points of edge 4 : 1 4
Enter the end-points of edge 5 : 1 3
The required vertex cover is as follows:
1 2 3 4

この例では頂点1〜4のすべてが解として出力されました。入力グラフが複数の閉路を含んでいるため、各ステップで選んだ辺の両端を追加していくと全頂点が必要になったケースです。グラフの形状によっては、より少数の頂点で被覆できる場合もあります。

計算量と注意点

この貪欲法の計算量は頂点数をV、辺数をEとするとO(V+E)程度と非常に高速で、大きなグラフにも適用できます。ただし、得られる解は必ずしも最小の頂点被覆ではなく、最適解の高々2倍程度の大きさになることが知られています（2近似アルゴリズム）。厳密な最小解が必要な場合は、整数計画法やバックトラッキングなどの手法と組み合わせる必要があります。