Pythonで無向グラフに指定サイズの独立集合が含まれるかどうかを確認する方法

ある無向グラフが与えられたとき、そのグラフの中に指定したサイズ l の独立集合(Independent Set)が含まれているかどうかを判定します。条件を満たす独立集合が存在すれば「Yes」を、存在しなければ「No」を出力します。

独立集合とは?

グラフ理論において独立集合とは、「互いに直接つながっていない(隣接関係にない)頂点だけで構成される集合」を指します。つまり、集合の中から任意の2つの頂点を選んだとき、その間に辺(エッジ)が存在してはいけません。

例として、L = 4 の場合を考えてみましょう。

このグラフの場合、出力は「Yes」となります。

解決のためのアプローチ

この問題はバックトラッキングを用いて解くことができます。手順は以下のとおりです。

• 関数 is_valid() を定義します。引数として graph と arr を受け取ります。

• i を 0 から arr のサイズ未満までループさせます。

• j を i + 1 から arr のサイズ未満までループさせます。

• graph[arr[i]][arr[j]] が 1(辺が存在する)であれば False を返します。

• すべての頂点ペアに辺が見つからなければ True を返します。

• 関数 solve() を定義します。引数として graph、arr、k、index、sol を受け取ります。

• k が 0 になったら、is_valid(graph, arr) の結果が True である場合に sol[0] に True を代入して処理を終了します。

• それ以外の場合、index >= k であれば「頂点 index を集合に追加する場合」と「追加しない場合」の両方を再帰的に探索し、index < k の場合は「追加する場合」のみを探索します。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def is_valid(graph, arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if graph[arr[i]][arr[j]] == 1:
                return False
    return True


def solve(graph, arr, k, index, sol):
    if k == 0:
        if is_valid(graph, arr) == True:
            sol[0] = True
        return
    else:
        if index >= k:
            return (solve(graph, arr[:] + [index], k - 1, index - 1, sol)
                    or solve(graph, arr[:], k, index - 1, sol))
        else:
            return solve(graph, arr[:] + [index], k - 1, index - 1, sol)


graph = [
    [1, 1, 0, 0, 0],
    [1, 1, 1, 1, 1],
    [0, 1, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 1]]
k = 4
arr = []
sol = [False]
solve(graph, arr[:], k, len(graph) - 1, sol)
if sol[0]:
    print("Yes")
else:
    print("No")

入力

[[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 1, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 1]],
4

出力

Yes

なぜ「Yes」になるのか

上記の隣接行列では、頂点 0・2・3・4 の間に互いに辺が存在しません。したがって、これら4つの頂点からなる集合 {0, 2, 3, 4} がサイズ4の独立集合となり、プログラムは「Yes」を出力します。

計算量に関する注意点

指定サイズの独立集合の存在判定は、NP困難として知られる最大独立集合問題に関連しています。バックトラッキングによる探索は最悪の場合 O(2^n) の指数時間を要するため、この手法は頂点数が比較的少ないグラフに適しています。