最大クリーク問題で面白いなとおもったこと

いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。
ある無向グラフGについて \omega(G)を最大クリークサイズを返す関数とする。

f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフを G_iとすると
\omega(G) = \sum \omega(G_i)

g(m) : グラフが非連結で、連結グラフn個に分かれているとする、その各グラフを G_iとすると
\omega(G) = \max \{ \omega(G_i) \}

h(k) : 頂点をうまく分割するとサイズkのクリーク c \in C^k( C^kはサイズkのクリークの集合)と、その全点から接続している頂点 V_cとそれ以外。

\displaystyle \omega(G) = \omega(c^k) + \omega(G[V_c]) + \alpha, c^k \in C^k
V_c = \emptyset となるのが極大クリーク。

上記を踏まえ、判定式 \omega_kをつくる

f(w)のうち、補グラフで孤立点(元のグラフでは自身を除く全点と接続)となっているものを取り出す処理をp(n)とする。 O(n)で処理できる。

\displaystyle \omega_k(G) = \omega_a(A) + \omega_{k-a}(G [ V \setminus A ]), A = \{v \in V \,|\, d(v) = |V| - 1 \}

h(k)はk=2に固定した h_2 = \omega_2とp(n)と畳み込み使って、下記のように表すことができる。

\omega_k(G) = \max_{e \in E} \{ \omega_2(e) + \omega_{k-2}(G[V_e]) \} = h_2 \ast p

g(m)については h_2が、Eを順次探索するのでその時に一緒にやってしまえる(実装では辺に対してBFS, クリークに対してDFSとなっている)のであまり考えなくてよい。f(w)の孤立点以外については実装は簡単(UnionFind)でできるけど、そのケースにどれくらい当てはまるかが微妙なのと補グラフの辺はもっていないので O(n^2)掛けてつくるかが微妙、濃度に合わせてやるのが良さそうという感じをもっている。

とりあえずABC002 派閥で試してhttp://abc002.contest.atcoder.jp/submissions/1271432はRubyでは最速になってた。C++と比べるとおそいけどスピンアップの時間考えるとかなり速いと思う。
Cのコード見てると隣接行列使って解いてるっぽいコードがあった。すげぇ早い

メモ: 下記の論文によると補グラフのBFSやDFSを O(n+M), m + M = \frac{n(n-1)}{2}でできるらしい。なら、やればよいかという気がしている。

http://www.orsj.or.jp/~archive/pdf/a_a/1995A_228.pdf