最大クリーク問題

最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。

この問題は、補グラフに対する最大独立集合問題と等価である。

近似アルゴリズムについても研究されているが、グラフの頂点数を  とするとき、近似度  が達成されているのみである。また、P = NP が成り立たないとき、任意の  について、近似度  の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度  の近似アルゴリズムが存在しないことも示されている。

 脚注 

参考文献


関連項目
 NP完全
 計算複雑性理論（計算量理論）

外部リンク
 最大クリーク問題を解くアルゴリズムのデモ

Category:計算複雑性理論
Category:グラフ理論
Category:数学の問題
Category:数学に関する記事

fr:Clique (théorie des graphes)#Problème de la clique