最大クリークの計算量とか
修正しました。
kousuke.hatenablog.com
(以下、古い内容)
をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)
最大サイズkのクリークを含む、単純な無向グラフがあるとする。頂点vに隣接している頂点の集合をとし、に対し、とする。ならば、eを含むサイズ3のクリークが存在し、誘導部分グラフの中にeを含むクリークが全て含まれる。よって次式が成り立つ。
の頂点はすべてeに接続しているので、にサイズk-2のクリークがあればよいので、さらに次式のように変形できる。
前式によりは再帰的に求めることができることがわかる。
先程のの表記を拡張して、単にサイズcのクリークをと表記し、その全点から接続している頂点の集合をと書くことにすると、再帰の深さtを用いて次のように変形できる。
にサイズkのクリークが含まれない場合、eを消しても最大クリークには影響しない。Gからi個の辺を除去したものをとすると次式のように変形できる。iはに含まれる辺の最小のインデックスの意。
終了条件も合わせて下記のようになる。
深さk/2の有界探索木だとおもうので、そうするとだとおもう。
これに加えてサイズkのクリークはk-1以上の次数を必ず持つので次数k-1未満の点を除去していってもなくならない。この処理をとすると下記が成り立つ*1。
この前処理の結果、次数がk-1未満の頂点は全てなくなる。特にkが最大クリークサイズよりそれなりに大きい場合はとなり、前処理の中で完全に解けることになる(FPT?)。
また辺を評価する処理が進むにつれて辺はなくなっていき次数がk-1未満になる点はその時点で除去できる。
そのため、すべての辺を評価しなくとも、各頂点で個の辺だけ評価すればよい。
もうひとつパラメーターがあって、それが極大クリークの数になる。これをwとするとtに対し、w'≦wなんだけどこれを上手く処理できると多項式の目が出てくるかなと思っている。
補グラフの辺を変わりに評価対象にすればよいだろうか。
*1:これ自体は彩色問題でも成立する