最大クリーク問題のソースを表示

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

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

[[近似アルゴリズム]]についても研究されているが、グラフの頂点数を n とするとき、[[近似度]] O(n / (log n)^2) が達成されているのみである。また、P=[[NP]] が成り立たないとき、任意の ε>0 について、近似度 n^(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=[[ZPP]]が成り立たない場合、近似度 n^(1-ε) の近似アルゴリズムが存在しないことも示されている。

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

==外部リンク==
*[http://www.nada.kth.se/~viggo/wwwcompendium/node33.html MAXIMUM CLIQUE]
*[http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/demo/MaxClique/ 最大クリーク問題を解くアルゴリズムのデモ]

{{デフォルトソート:さいたいくりいくもんたい}}
[[Category:計算複雑性理論]]
[[Category:グラフ理論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]

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