最大クリーク問題(改)

最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。

補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。

補グラフをk彩色できたら、かけてで色クラスを2つ選んで最大マッチングで最小頂点被覆を求めて、最大独立集合を求めて少しずつ大きくしていく。
もしk=2になったら確定する。

k≧3から落ちなければ、微妙。ただ、ある程度の大きさまで来たら、補グラフの連結性を判定して細切れの補グラフ連結成分の元グラフのクリークサイズで足し合わせることができるので、そこがカーネルになるなら、それはそれであり。

補グラフを彩色するのは最適彩色じゃなくてよいので、Welsh-Powellの貪欲彩色とか、外部性のある安定結婚問題とかで解ける。
むしろ最適だとn/kに近くなっちゃうので、頂点数最大になるような方法の方がよい。まあ、その方法はNP完全なんだけどね。