C++で無向グラフが指定されたサイズの独立集合を含むかどうかを判定する方法

概念

与えられた無向グラフに対して、サイズ l の独立集合（Independent Set）が含まれているかどうかを判定します。独立集合が存在する場合は「Yes」を、存在しない場合は「No」を出力します。

ここで、グラフにおける独立集合とは、「互いに直接辺で結ばれていない頂点の集合」のことです。つまり、集合内のどの2つの頂点を選んでも、それらの間にエッジ（辺）が存在しない必要があります。

入力例 1

L = 4,
graph = [[1, 0, 1, 0, 0],
[0, 1, 1, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 1, 0],
[0, 0, 1, 0, 1]];

出力例 1

Yes

上記のグラフには、サイズ 4 の独立集合が存在します（頂点 0、1、3、4 は互いに直接接続されていません）。したがって、出力は「Yes」となります。

入力例 2

L = 4,
graph = [[1, 1, 1, 0, 0],
[1, 1, 1, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 1, 0],
[0, 0, 1, 0, 1]];

出力例 2

No

この図のグラフには、サイズ 4 の独立集合は存在しません。そのため、出力は「No」となります。

アルゴリズムの考え方

• まず、ブール値 False で初期化された変数 sol を用意します。
• 与えられたグラフから、サイズ L の頂点集合として考えられるすべての組み合わせを生成します。
• サイズ l の独立集合が見つかった場合は、sol の値を True に変更して処理を終了します。
• 見つからない場合は、他の候補となる頂点集合の探索を続けます。
• 最終的に、sol が True であれば「Yes」を、そうでなければ「No」を出力します。

この問題は、組み合わせを再帰的に生成するバックトラッキングの手法で解くことができます。各頂点について「選ぶ」「選ばない」という2択を繰り返しながら、条件を満たす集合を探索していきます。

C++実装例

// グラフがサイズ k の独立集合を
// 含むかどうかを判定する C++ コード
#include <bits/stdc++.h>
using namespace std;

// 関数プロトタイプ宣言
bool check1(int[][5], vector<int>&, int);

// サイズ l の集合を構築する関数
bool func(int graph1[][5], vector<int>&arr1,
int l, int index1, bool sol1[]){
    // 選択された集合が独立であるかどうかを確認。
    // 独立であれば sol を True に変更して return
    if (l == 0){
        if (check1(graph1, arr1, arr1.size())){
            sol1[0] = true;
            return true;
        }
    }
    else{
        // 現在のインデックスの頂点を含めなくても、
        // サイズ l の集合を形成できる場合
        if (index1 >= l){
            vector<int> newvec(arr1.begin(), arr1.end());
            newvec.push_back(index1);
            return (func(graph1, newvec, l - 1,
            index1 - 1, sol1) or
            func(graph1, arr1, l, index1 - 1, sol1));
        }
        // 現在のインデックスの頂点を含めないと、
        // サイズ l の集合を形成できない場合
        else{
            arr1.push_back(index1);
            return func(graph1, arr1, l - 1,
            index1 - 1, sol1);
        }
    }
}

// 与えられた集合が独立であるかどうかを
// 検証する関数
// arr --> サイズ l の集合（含まれる頂点の
// インデックスを保持）
bool check1(int graph1[][5], vector<int>&arr1, int n1){
    // 集合内の各頂点が他のどの頂点とも
    // 接続されていないことを確認
    for (int i = 0; i < n1; i++)
        for (int j = i + 1; j < n1; j++)
            if (graph1[arr1[i]][arr1[j]] == 1)
                return false;
    return true;
}

// ドライバーコード
int main(){
    int graph1[][5] = {{1, 0, 1, 0, 0},{0, 1, 1, 0, 0},{1, 1, 1, 1, 1},{0, 0, 1, 1, 0},
    {0, 0, 1, 0, 1}};
    int l = 4;
    vector<int> arr1; // 空の集合
    bool sol1[] = {false};
    int n1 = sizeof(graph1) /
    sizeof(graph1[0]);
    func(graph1, arr1, l, n1 - 1, sol1);
    if (sol1[0])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

出力結果

Yes

コードのポイント

この実装では、func 関数が再帰的に頂点の組み合わせを生成し、check1 関数が選ばれた頂点同士が隣接行列上で接続されていないか（独立集合の条件を満たすか）を二重ループで検証します。計算量は組み合わせの総数に依存するため O(2ⁿ) オーダーとなり、頂点数が多いグラフでは指数関数的に増加することに注意が必要です。