最大クリーク問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
このグラフは最大クリーク {1, 2, 5} を持つ

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

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

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

脚注[編集]

参考文献[編集]

関連項目[編集]

外部リンク[編集]