Day 036-Q4 | 最大クリーク — Bron-Kerbosch + 補グラフ疎

問題

$N$ 頂点の無向グラフ $G$ の 最大クリーク サイズを求めよ。ただし，補グラフの辺数 $\bar{M} \le 10^5$（補グラフが疎）であることが保証される。入力は補グラフの辺を与える。

制約

$2 \le N \le 10^5$

$0 \le \bar{M} \le 10^5$

補グラフの辺を入力

自己ループ・重複辺なし

入出力例

入力例 1

出力例 1

補グラフの非辺: {1-3, 2-4, 3-5}。元グラフのクリーク {1,2,4,5} がサイズ4。

概念図: 元グラフ vs 補グラフ

ヒント (段階的開示)

ヒント1: 問題変換

元グラフの最大クリーク = 補グラフの最大独立集合。補グラフが疎（$\bar{M}$ 小さい）→ Bron-Kerbosch が実用的に高速。

ヒント2: Bron-Kerbosch の構造

$R$: 現クリーク候補，$P$: 追加可能，$X$: 処理済み。
$P = \emptyset$ かつ $X = \emptyset$ → 極大クリークを発見。
ピボット選択: $P \cup X$ から「$P$ との元グラフ隣接が最大の頂点」を選ぶ。

ヒント3: 枝刈り

# 枝刈り: 残り候補 + 現クリーク <= 現在最大
if len(R) + len(P) <= max_clique[0]:
    return
# ピボット選択
pivot = max(P | X, key=lambda v: len(P - adj_bar[v]))

模範解答 (Python)

import sys
from sys import setrecursionlimit
input = sys.stdin.readline

def solve():
    setrecursionlimit(300000)
    N, Mbar = map(int, input().split())

    adj_bar = [set() for _ in range(N + 1)]
    for _ in range(Mbar):
        u, v = map(int, input().split())
        adj_bar[u].add(v)
        adj_bar[v].add(u)

    max_clique = [0]

    def bk(R, P, X):
        if not P and not X:
            if len(R) > max_clique[0]:
                max_clique[0] = len(R)
            return
        if len(R) + len(P) <= max_clique[0]:
            return
        pivot = max(P | X, key=lambda v: len(P - adj_bar[v]))
        for v in list(P - adj_bar[pivot]):
            new_P = P - adj_bar[v] - {v}
            new_X = X - adj_bar[v]
            bk(R | {v}, new_P, new_X)
            P.discard(v)
            X.add(v)

    bk(set(), set(range(1, N + 1)), set())
    print(max_clique[0])

solve()

Step-by-Step 解説

1問題変換
元グラフ最大クリーク = 補グラフ最大独立集合。補グラフが疎のため Bron-Kerbosch が有効。

2Bron-Kerbosch
$P - \text{adj\_bar}[v]$ = $v$ の元グラフ隣接頂点（補グラフ非隣接）。これが新しい $P$ となる。

3ピボット選択
$P \cup X$ から「$P$ との元グラフ隣接が最多の頂点」を選ぶ（= 補グラフ隣接が最少）。これにより探索木のブランチ数を減らす。

4枝刈り
len(R) + len(P) ≤ max_clique[0] なら探索を打ち切る。

計算量

最悪: $O(3^{N/3})$（NP困難）
補グラフ疎の場合: 実用的には $O(\bar{M}^{O(1)})$ 程度に収まる
最大クリークサイズは $O(\sqrt{\bar{M}})$ 程度

よくあるミス

ミス	原因	正しい書き方
元グラフと補グラフの混同	`adj_bar[v]` = 補グラフ隣接	コメントを明記
ピボット選択の基準誤り	`len(P - adj_bar[v])` 最大 (= 元グラフ隣接最多)	`max(P\|X, key=...)`
P を in-place 変更でループ破壊	反復中に P を変更	`for v in list(P - adj_bar[pivot]):`
再帰制限	N が大きい	`setrecursionlimit` を設定

次のステップ

発展: 最大クリーク列挙，または coloring upper bound による枝刈り強化
応用: 補グラフが密の場合は Bron-Kerbosch では困難 → 近似アルゴリズム

自己評価

完全理解おおむね理解要復習

Day 036-Q4 — 最大クリーク (Bron-Kerbosch + 補グラフ疎)

問題

制約