最大クリークの計算量とか - 高温処理済みコースケ

(以下、古い内容)

$\omega_k(G)$ をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)

最大サイズkのクリークを含む、単純な無向グラフ $G (|V| = n, |E| = m)$ があるとする。頂点vに隣接している頂点の集合を $adj(v)$ とし、 $e = \{u, v\}$ に対し、 $V_e = adj(u) \cap adj(v)$ とする。 $V_e \ne \emptyset$ ならば、eを含むサイズ3のクリークが存在し、誘導部分グラフ $G[V_{e} \cup e]$ の中にeを含むクリークが全て含まれる。よって次式が成り立つ。

$\omega_k(G) = \max_{e \in E}\,\{\, \omega_{k}(G[ V_e \cup e ]) \, \}$

$V_{e}$ の頂点はすべてeに接続しているので、 $G[ V_{e} ]$ にサイズk-2のクリークがあればよいので、さらに次式のように変形できる。

$\omega_k(G) = \max_{e \in E} \> \{ \> \omega_{k - 2}(G[ V_{e} ])\, \}$

前式により $\omega_k$ は再帰的に求めることができることがわかる。

先程の $V_e$ の表記を拡張して、単にサイズcのクリークを $C_{|c|}$ と表記し、その全点から接続している頂点の集合を $V_{|c|}$ と書くことにすると、再帰の深さtを用いて次のように変形できる。

$\omega_k(G) = \max_{C_{|2t|} \, \subset \, G} \> \{ \omega_{k - 2t}({G}[ V_{|2t|} ]),\hspace{2ex} 2t \le k \}$

$G[V_{e} \cup e]$ にサイズkのクリークが含まれない場合、eを消しても最大クリークには影響しない。Gからi個の辺を除去したものを $G_i = G - \{e_0,e_1,\dots,e_{i-1}\}$ とすると次式のように変形できる。iは $G[ V_{|2t|} ]$ に含まれる辺の最小のインデックスの意。

$\omega_k(G) = \max_{C_{|2t|} \, \subset \, G} \> \{ \omega_{k - 2t}({G_i}[ V_{|2t|} ]),\hspace{2ex} 2t \le k\}$

終了条件も合わせて下記のようになる。

$\displaystyle \omega_0(G) = \text{always} \, 1\\ \omega_1(G) = \begin{cases} 1 \hspace{10em} (n \gt 0) \\ 0 \hspace{10em} (n = 0) \\ \end{cases}\\ \omega_2(G) = \begin{cases} 1 \hspace{10em} (m \gt 0) \\ 0 \hspace{10em} (m = 0 ) \\ \end{cases}\\ \omega_k(G) = \begin{cases} 0 \hspace{10em} (n \lt k) \\ 0 \hspace{10em} (2m \lt k(k-1)) \\ 1 \hspace{10em} (G = K_n ,\hspace{2ex} n \ge k)\\ \max \> \{\omega_{2t}(C_{|2t|})\, \omega_{k - 2t}({G_i}[ V_{|2t|} ]) \} \end{cases}\\$

深さk/2の有界探索木だとおもうので、そうすると $\mathbb{O}(2^{\frac{k}{2}}m)$ だとおもう。

これに加えてサイズkのクリークはk-1以上の次数を必ず持つので次数k-1未満の点を除去していってもなくならない。この処理を $f_{k-1}: G \rightarrow G'$ とすると下記が成り立つ*1。

$\omega_k(G) = \omega_k(f_{k-1}(G))$

この前処理の結果、次数がk-1未満の頂点は全てなくなる。特にkが最大クリークサイズよりそれなりに大きい場合は $f_{k-1}(G) = K_0$ となり、前処理の中で完全に解けることになる(FPT?)。

また辺を評価する処理が進むにつれて辺はなくなっていき次数がk-1未満になる点はその時点で除去できる。
そのため、すべての辺を評価しなくとも、各頂点で $d(v) - (k - 2)$ 個の辺だけ評価すればよい。

もうひとつパラメーターがあって、それが極大クリークの数になる。これをwとするとtに対し、w'≦wなんだけどこれを上手く処理できると多項式の目が出てくるかなと思っている。

補グラフの辺を変わりに評価対象にすればよいだろうか。

*1:これ自体は彩色問題でも成立する