植え付けられた派閥

関数が存在する${\displaystyle f(n)\sim 2\log _{2}n}$漸近的にほぼ確実に、 n頂点ランダムグラフにおける最大のクリークのサイズは、${\displaystyle f(n)}$または${\displaystyle f(n)+1}$^{[ 2 ]}そして、ある定数が存在する${\displaystyle c}$期待されるクリークの数が${\displaystyle \geq f(n)-c}$無限大に収束する。したがって、サイズのクリークを植えると、${\displaystyle \sim 2\log _{2}n}$高い確率で検出できない。

中心極限定理によれば、ランダムグラフの頂点次数は、平均が標準正規分布に近い分布を示す。${\displaystyle {\frac {n}{2}}}$標準偏差$\displaystyle {\frac {\sqrt {n}}{2}}}$したがって、${\displaystyle k}$オーダーとしては${\displaystyle {\sqrt {n}}}$これは分布の形状に検出可能な変化をもたらします。つまり、頂点次数分布をプロットすると、変形したベルカーブのように見えます。したがって、パラメータkの値の最も興味深い範囲は、次の 2 つの値の間です。^{[ 1 ]}

$\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}.}$

パラメータkの値が十分に大きい場合、植栽クリーク問題は（高い確率で）多項式時間で解くことができる。^{[ 1 ]}

Kučera (1995) は、次のことを観察しています。${\displaystyle k=\Omega ({\sqrt {n\log n}})}$すると、ほぼ確実に、植え付けられたクリークのすべての頂点の次数は、クリーク外のすべての頂点の次数よりも高くなり、クリークを見つけるのが非常に簡単になります。彼は、植え付けられたクリークのインスタンスを生成するランダムプロセスに対する修正について説明しており、kの値が大きい場合でも頂点の次数がより均一になりますが、この修正にもかかわらず、植え付けられたクリークは依然として迅速に見つかる可能性があることを示しています。^{[ 3 ]} 

アロン、クリヴェビッチ、スダコフ (1998)は次のことを証明しています。${\displaystyle k>10{\sqrt {n}}}$仕組まれた派閥は、以下の方法によって高い確率で発見できる。

1. 隣接行列の2番目に高い固有値に対応する固有ベクトルを計算します。
2. この固有ベクトル内の座標の絶対値が最大となるk個の頂点を選択します。
3. 選択された頂点の少なくとも4分の3に隣接する頂点の集合を返します。

彼らは、 k が頂点数の平方根の何倍かに比例する限り、この手法が機能し続けるように修正する方法を示している。 ^{[ 4 ]}大規模な植え付けクリークは、半正定値計画法を使用して見つけることもできる。^{[ 5 ]}頂点をランダムにサンプリングすることに基づく組み合わせ的手法は、 k に関して同じ上限を達成でき、線形時間で実行される。^{[ 6 ]}

kの選択に関係なく、植え付けクリーク問題を準多項式時間で解くことも可能です。^{[ 7 ]} ランダムグラフにおける最大のクリークのサイズは通常2 log ₂ nに近いので、^{[ 8 ]}サイズkの植え付けクリーク(存在する場合) は次の方法で高い確率で見つけることができます。

1. すべてのセットSをループします${\displaystyle \min(k,3\log _{2}n)}$頂点。
2. Sの各選択肢について、Sがクリークであるかどうかをテストします。もしそうであれば、${\displaystyle |S|=k}$、Sを返します。そうでない場合は、 Sのすべての頂点に隣接する頂点の集合Tを見つけます。${\displaystyle |T|\geq k}$Tを返します。

このアルゴリズムの実行時間は準多項式時間です。なぜなら、ループ処理するSの選択肢が準多項式個存在するからです。この方法では、植え付けられたクリークの部分集合である集合Sを必ず試行します。高い確率で、集合Tは植え付けられたクリークの他のメンバーのみで構成されます。