最大クリーク問題の現在

Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースで O^\ast(2^{\frac{k}{2}})がはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。

大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあった

www.slideshare.net




https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-53-638.jpg?cb=1363753229

最大クリークの計算量とか(続き) - 高温処理済みコースケでも書いてたのとほぼ同じ形になっていったため、この畳み込みの式をみて、方向性はわるくないことがわかった。

 \displaystyle
\omega_k(G) = \begin{cases}
0 & (n \lt k) \\
0 & (2m \lt k(k-1)) \\
\omega_{k - a}(G[ V \setminus A ]) & (A \ne \emptyset) \\
\max_{e \in E} \> \{ \, \omega_{k - 2}(G[ V_{e} ])\, \} & \\
\end{cases}


https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-44-638.jpg?cb=1363753229

辺の重みは自分で作って、それを修正する形で最大クリークサイズをもとめればいいことに気づいた。
辺の重みは w(e) = |V_e| + 2にして、 |V_e| \ge \omega(G[V_e])の関係を利用する。


凸関数どうやって作ればよいか悩んだ。
https://image.slidesharecdn.com/slide-130320033020-phpapp01/95/-26-638.jpg?cb=1363753229

最初は二分探索してて、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