最大クリーク問題

最大クリーク問題

与えられたグラフ $G$ の最大クリークを求める NP 困難な最適化問題である.

最大クリークとは

グラフ $G$ の「クリーク clique」とは, 頂点部分集合 $C \subseteq V(G)$ で, $C$ のどの 2 頂点も辺で結ばれているものをいう. すなわち, $G$ において $C$ が誘導する誘導部分グラフ $G[C]$ は完全グラフである.

• クリーク $C$ の頂点数 $|C|$ のことを $C$ の「大きさ」といい,

大きさ $k$ のクリークを「$k$ クリーク $k$-clique」と呼ぶ.

• $G$ の任意のクリーク $C$ に対して,

$|C'| \geq |C|$ を満たすようなクリーク $|C'|$ を $G$ の「最大クリーク maximum clique」という. 最大クリークの大きさを $G$ の「クリーク数 clique number」と呼ぶ.

• 自身を除く $G$ の任意ののクリークの部分集合でないようなクリークを「極大クリーク maximal clique」という.

たとえば, 上図のグラフにおいて, 極大クリークは $\{1, 2, 3\}$, $\{4, 5, 6, 7\}$ で, 最大クリークは $\{4, 5, 6, 7\}$ である. したがって, このグラフのクリーク数は 4 である.

最大クリークを見つけるアルゴリズム

たとえば, 適当な1頂点 (＝1クリーク) から深さ優先探索でクリークを拡大していき, 極大クリークを見つけていく. 極大クリークを見つけるたびに最大のものを記憶しておき, 探索終了後にそれを出力すればよい.

既に見つけたクリークに含まれる頂点は探索する必要がないことや, クリークの彩色数などを利用して分枝限定を行うことで効率化を図れる.

ABC002-D

AtCoder Beginner Contest 002 の D 問題「派閥」は, 与えられたグラフのクリーク数を求める問題となっている.