最大クリーク問題の現在
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