読者です 読者をやめる 読者になる 読者になる

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

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式では元のグラフの辺を選んでいて、すべての頂点は必ず補グラフの辺を1本以上含んでいるので、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かもしれない。