最大クリークの。。。

最大クリーク数をcとすると、の確率で最大クリークと一致する順序が得られるのか。。。同じサイズの極大クリークあればもっと良い確率になるけど。。

とりあえず下記でできる気がしてきた。

1. サイズcのクリークは次数c-1以上の頂点がc個必要(条件A)なので、次数c-1以上の頂点を出して誘導グラフを作ってというのを再帰的に行う。最終的にすべての頂点の次数がc-1以上になる。
2. 頂点数がcならこの時点でサイズcのクリークが見つかった。頂点数がcより多ければ、最大クリークを探すアルゴリズムを実行(それが課題なんだけどcarraghanのアルゴリズムでもよいか)。
3. やはりサイズcのクリークがなければ、cをひとつへらしてやり直し

かな。FPTになってる気がするので、1を終えた段階のグラフG'に対してにはなる。