最大クリーク問題つづき - 高温処理済みコースケ

グラフのDegeneracyをkとすると前処理後、おおまか $2^{k}n$ で最大クリークが求まるな。

Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフ $G(V,E)$ を順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。

最大出次数を $\Delta_+$ とする。

頂点が順序付けされたので、 $v$ を始点とするクリーク集合というのが扱えるようになった。
頂点 $v$ とその出力辺からなる隣接集合から誘導される部分グラフ $H_v$ に $v$ を始点とするクリーク集合がすべて含まれる。

この $H_v$ の $v$ を除く頂点の組み合わせをすべて試せば、vを含むクリークの最大サイズがわかる。
$\Delta_+$ は最小化されていて、n頂点すべてについて行うので、大まか $2^{\Delta_+} n$ でもとまる。

もうすこしアルゴリズムとして分解することにする。

頂点の冪集合 $P(V)$ のうち、特にサイズが $k$ のものを $P_k(V) \subset P(V)$ と書く。
$f$ をサイズkの頂点集合がクリークであればkを、そうでなければ-1を返すものとする。これは誘導部分グラフを作成し、頂点数と辺数から決めることができ多項式時間である。
$\displaystyle f: P_k(V) \rightarrow \{k,-1\}$

$T_v$ をある頂点 $v$ の出力辺から作成される隣接集合とすると、最大クリークをもとめる $\omega(G)$ は下記のような形になる。

$\displaystyle \omega(G) = \max_{v \in V} \max_{k=0,1,\cdots} \max\{\max \{ f(\{v\} \cup T_v \setminus X),\> f(\{v\} \cup X)\} | X \in P_{k}(T_v) \}$

上記の式は下限、上限から挟み撃ちにしている。

$f(\{v\} \cup T \setminus X) > 0$ となるときは、明らかに $v$ を始点とする最大クリークであり、次の頂点に移ればよい。最も内側のmax式が-1の時は、下でクリークが見つからないわけなので、そこまでに見つかった最大クリークサイズを返して、やはり次の頂点に移る。*1

判定式のほうはkを求めるクリークサイズとすると $d_+(v) - k,k$ の小さいほうを使用する。これを $k'$ とするとおおまか計算量は ${}_{\Delta_+}\mathrm{C}_{k'} n$ になる。
もちろん $k > \Delta_+$ であれば解はない。

$\displaystyle \begin{eqnarray} \omega(G,k) & = & \max_{v \in V} \max_{X \in P_{k}(T_v)} f(\{v\} \cup X) & \hspace{1cm} & (d_+(v) - t \ge k) \\ & = & \max_{v \in V} \max_{X \in P_{k'}(T_v)} f(\{v\} \cup T_v \setminus X) & \hspace{1cm} & (d_+(v) - t \lt k) \end{eqnarray}$

最悪のケースは $\frac{\Delta_+}{2} = \omega(G)$ のときで、例えば $K_2$ が50個あるようなグラフの補グラフだと思う。サイズ50のクリークが $2^{50}$ 個あって、98正則グラフなので $\Delta_+ = 98$ 。正確に半分ではないけどイメージは伝わると思う。これは補グラフが連結ではないことが頂点数、辺数からわかるので状況に合わせて必要な処理を組み込むことで平均的な時間はもっと高速化できる。
~~おそらくこのアルゴリズムはZPPである。~~
まとめ

~~自分の理解ではおそらくNP困難問題である最大クリーク問題がPであり、NP完全問題であるk-クリーク問題がFPTになった。~~
~~もし違う観点があるとすれば、~~最大クリーク問題が $f(\Delta_+)p(n)$ のFPTで、k-クリーク問題が $f(\Delta_+,k)p(n)$ のFPTという感じ。

最大次数やk-core数なんてデータの入力長に依存しないのでPだと思っている。が、アルゴリズムで設定された幅とみれば、それは指数時間なのかもしれない。

その他
従来のFTPの議論では最大クリークや最大独立集合にFPTがないといわれていたが、次数から引くというとのが盲点だったのかなと思った。
ただ無向グラフで $v$ を含むクリークの最大を全部数えるでも、おそらくここに行きつくので最大次数は最小化できないという意味で有向グラフに変換するというが転換だったなのかなと思う。

(以下、全部　たぶん)

P≠NP予想は否定したとおもう。
#PもPである。P=NPであったので多項式階層はすべて潰れた

そしてP=ZPPである。P=ZPPからZPP≠EXPTIMEになる。
P=NPなのでETH, SETHも否定した。

参考 : NP困難 - Wikipedia
参考: #P - Wikipedia
参考: P≠NP予想 - Wikipedia
参考: 多項式階層 - Wikipedia
参考 : Fixed Parameter Algorithms Open lectures for PhD students in computer science
参考: ZPP - Wikipedia

*1:ただ、なんとなく中央まで行くのではなくて、3分の1進めたところで下限のほうのクリークの集合から２つ選んで最大クリークを探すほうが良い気がする。