最大クリーク問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。
近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)^2) が達成されているのみである。また、P=NP が成り立たないとき、任意の ε>0 について、近似度 n^(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=ZPPが成り立たない場合、近似度 n^(1-ε) の近似アルゴリズムが存在しないことも示されている。
