最大独立集合

まだ選ぶかどうか決めていない頂点の集合をビットで持ちます。その中で次数が $1$ 以下の頂点があれば、それを選んで隣の頂点とともに取り除きます(そうしても答えの大きさは変わりません)。次数がすべて $2$ なら閉路だけが残っているので、どの頂点を選んでもかまいません。そうでなければ次数が最大の頂点 $v$ について、「 $v$ を選び、 $v$ とその隣を取り除く」「 $v$ を選ばず、 $v$ だけを取り除く」の 2 通りに分けて調べます。再帰は使いません。 $N$ は 40 程度までが目安です。

計算量の式は最悪の場合で、多くのグラフではずっと速く終わります。

最大クリーク(どの 2 頂点も辺で結ばれている頂点の集合のうち最大のもの)は、補グラフ(辺で結ばれている 2 頂点と結ばれていない 2 頂点を入れ替えたグラフ)の最大独立集合です。また、最大独立集合に入らない頂点の集合は、最小頂点被覆(どの辺も少なくとも一方の端が入っている頂点の集合のうち最小のもの)になります。

例:

n = 6
edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)]
S = max_independent_set(n, edges)
print(S)  # [0, 4]
print([v for v in range(n) if v not in S])  # 最小頂点被覆 [1, 2, 3, 5]

# 最大クリーク: 補グラフの最大独立集合
E = set((min(u, v), max(u, v)) for u, v in edges)
comp = [(u, v) for u in range(n) for v in range(u + 1, n) if (u, v) not in E]
print(max_independent_set(n, comp))  # [0, 1, 2, 3]

コード

def max_independent_set(n, edges):
    # 頂点 0..n-1、無向辺 edges = [(u, v), ...] のグラフの最大独立集合を 1 つ、昇順のリストで返す(n は 40 程度まで)
    # 自己ループのある頂点は選ばない
    adj = [0] * n
    ban = 0
    for u, v in edges:
        if u == v:
            ban |= 1 << u
        else:
            adj[u] |= 1 << v
            adj[v] |= 1 << u
    best = 0  # これまでに見つけた最大の独立集合
    st = [((1 << n) - 1) & ~ban, 0]  # (まだ決めていない頂点の集合, 選んだ頂点の集合) を積む
    while st:
        C = st.pop()
        S = st.pop()
        while S:
            # 次数 1 以下の頂点があれば選ぶ。次数がすべて 2 なら閉路だけなので、どれを選んでもよい
            T = S
            mv = md = -1
            while T:
                b = T & -T
                T ^= b
                v = b.bit_length() - 1
                d = (adj[v] & S).bit_count()
                if d <= 1:
                    mv = v
                    md = d
                    break
                if d > md:
                    mv = v
                    md = d
            if md >= 3:
                break
            C |= 1 << mv
            S &= ~(adj[mv] | 1 << mv)
        if S:
            # 次数が最大の頂点 mv を、選ばない場合と選ぶ場合に分ける
            st.append(S & ~(1 << mv))
            st.append(C)
            st.append(S & ~(adj[mv] | 1 << mv))
            st.append(C | 1 << mv)
        elif C.bit_count() > best.bit_count():
            best = C
    return [v for v in range(n) if best >> v & 1]