最大クリークの途中で補グラフが出てくる話

kousuke.hatenablog.com
前回、ワーストケースで $\mathbb{O}(2^{\frac{k}{2}}(m - \frac{k-2}{2} n))$ になると書いた。

FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか?
簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。

最大クリーク判定の式をおさらいする。 $A$ は自身を除く全点に接続している頂点。
$\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}$

3番目をA式、4番目をB式と呼ぶ。

A式では全点につながった辺はまとめて処理でき、ここは分岐する必要がない。また、この処理で辺は一気に減っているけど、補グラフの辺は実は減ってない。このことからも極大クリークを示すのに適当そうな感じがする。またA式の処理により、B式を処理するときには、すべての頂点は必ずどこかの頂点とつながっていない。そのため、補グラフに辺がある。ということでここから補グラフで展開していく。

補グラフの辺の数をwとする。 $w = \frac{n(n-1)}{2} - m$ となる。

D式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を１本以上含んでいるので、D式処理後、必ず補グラフの辺は2つ以上減る。
計算量はざっと $O(2^{\frac{w}{2}}(m-\frac{k-2}{2}n))$ が想定される。
とはいえワーストケースがk/2で収まるので、準指数 $O(2^{\sqrt{2w}}(m-\frac{k-2}{2}n))$ でも大きそう。

なのでP=NPか、P≠NPでも、比較的小さいところで $\log w$ より小さくなる関数じゃないかとおもっている。もしかすると虚数がでてきて、k/2とどちらか速い方の可能性もある。

最小頂点被覆の計算量で $C^n \ge C^{n-1} + C^{n-3}$ が示せればよいとしてCを求めるやつだと、そのままwに置き換えると $C^w \ge C^{w-2}$ になるんで $C \ge 1$ か、1ならP=NPかもしれない。