続(4) - 最大クリーク問題
多分4じゃないかと思う。ナンバリングは適当
グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ
補グラフが非連結も同様
すげぇコンパクトになるんですけどって感じだ。
これが何につながるかというと最大クリーク問題なわけで、例えば頂点数100で、補グラフがのような非連結のグラフのとき、元のグラフではサイズ50のクリークが個あるわけだけど、補グラフで考えると一気に頂点2 * 連結成分50の問題になる。
とはいえ、きっとよく知られた内容だとおもうんだけど、自分的にはこれは結構すごいなと感動した。
最大クリーク問題の現在
Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースでがはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。
大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあった
www.slideshare.net
最大クリークの計算量とか(続き) - 高温処理済みコースケでも書いてたのとほぼ同じ形になっていったため、この畳み込みの式をみて、方向性はわるくないことがわかった。
辺の重みは自分で作って、それを修正する形で最大クリークサイズをもとめればいいことに気づいた。
辺の重みはにして、の関係を利用する。
最初は二分探索してて、Dinkelbachにしたいんだけどって感じで。。。でも、g(t)を支える直線に沿って進むのがイメージしにくかったのと、比じゃないしとおもっていて困っていた。
結果、まあ納得いくソースになった。特に超denseのときにもつらくないのがよい。
判定ならn = 200, m = 4565, k = 14を探すのに2.74秒、プログラミングコンテストの問題とかでも行けそう。
$ time bin/max_clique -k 14 < fixtures/clique/N200M4565C14.txt 14 9 11 13 47 52 57 61 90 126 150 158 170 180 192 real 0m2.749s user 0m0.030s sys 0m0.015s
最大クリーク問題で面白いなとおもったこと
いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。
ある無向グラフGについてを最大クリークサイズを返す関数とする。
f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフをとすると
g(m) : グラフが非連結で、連結グラフn個に分かれているとする、その各グラフをとすると
h(k) : 頂点をうまく分割するとサイズkのクリーク(はサイズkのクリークの集合)と、その全点から接続している頂点とそれ以外。
となるのが極大クリーク。
上記を踏まえ、判定式をつくる
f(w)のうち、補グラフで孤立点(元のグラフでは自身を除く全点と接続)となっているものを取り出す処理をp(n)とする。で処理できる。
h(k)はk=2に固定したとp(n)と畳み込み使って、下記のように表すことができる。
g(m)についてはが、Eを順次探索するのでその時に一緒にやってしまえる(実装では辺に対してBFS, クリークに対してDFSとなっている)のであまり考えなくてよい。f(w)の孤立点以外については実装は簡単(UnionFind)でできるけど、そのケースにどれくらい当てはまるかが微妙なのと補グラフの辺はもっていないので掛けてつくるかが微妙、濃度に合わせてやるのが良さそうという感じをもっている。
とりあえずABC002 派閥で試してhttp://abc002.contest.atcoder.jp/submissions/1271432はRubyでは最速になってた。C++と比べるとおそいけどスピンアップの時間考えるとかなり速いと思う。
Cのコード見てると隣接行列使って解いてるっぽいコードがあった。すげぇ早い
メモ: 下記の論文によると補グラフのBFSやDFSをでできるらしい。なら、やればよいかという気がしている。
補グラフでの最小頂点被覆ってなんだろう?
補グラフでの最小頂点被覆ってなんだろう?って考えてて、最大クリークの頂点以外の頂点集合って意味しかないのかな
最大クリークの途中で補グラフが出てくる話
kousuke.hatenablog.com
前回、ワーストケースでになると書いた。
FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか?
簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。
最大クリーク判定の式をおさらいする。は自身を除く全点に接続している頂点。
3番目をA式、4番目をB式と呼ぶ。
A式では全点につながった辺はまとめて処理でき、ここは分岐する必要がない。また、この処理で辺は一気に減っているけど、補グラフの辺は実は減ってない。このことからも極大クリークを示すのに適当そうな感じがする。またA式の処理により、B式を処理するときには、すべての頂点は必ずどこかの頂点とつながっていない。そのため、補グラフに辺がある。ということでここから補グラフで展開していく。
補グラフの辺の数をwとする。となる。
D式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を1本以上含んでいるので、D式処理後、必ず補グラフの辺は2つ以上減る。
計算量はざっとが想定される。
とはいえワーストケースがk/2で収まるので、準指数でも大きそう。
なのでP=NPか、P≠NPでも、比較的小さいところでより小さくなる関数じゃないかとおもっている。もしかすると虚数がでてきて、k/2とどちらか速い方の可能性もある。
最小頂点被覆の計算量でが示せればよいとしてCを求めるやつだと、そのままwに置き換えるとになるんでか、1ならP=NPかもしれない。