俺のFPTの理解

FPTにおいては幅とパラメータが存在する。

たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。
k-クリーク判定では幅hに対しての組み合わせになるので二項定理から {}_{h}\mathrm{C}_{k} = {}_{h}\mathrm{C}_{h-k}なので、 min(k,h-k)を用いて h^{min(k,h-k)}のオーダーで上限を決めることができる。

今回、最大クリーク問題の幅をk-coreとしたが、その幅は彩色数の近似にもできる。
k-coreの順序で貪欲彩色することにより、k-core + 1以下の彩色結果が得られるので、それを幅にしてもよい。
その場合でも上限は幅をもとに計算することができる。

W[1]-completeとはおそらくこの幅hとパラメータkの2変数により f(h,k)p(n)となるものだと考える。幅はアルゴリズム上設定されたもので、kは判定問題に与えられるパラメータ。これが指数関数しかないのか、多項式のものもあるのかはまだわからない。探索木を多項式時間で検索できればよい。結構制限はあるなかでの探索なのでもしかすると多項式時間のアルゴリズムがあるかもしれない。

指数時間アルゴリズム入門だと100万頂点からサイズ30以下の頂点被覆を求めることが可能ってなってたけど、補グラフの最大クリークのサイズをnから引いたものが頂点被覆なわけだから、幅hに対してk,h-kが小さければ、もっと全然できるはず。

Clique problem - Wikipedia 英語のWikiPediaの記事でDegeneracyをつかって最大クリーク問題ができるのが書いてあるな。

指数時間アルゴリズム入門だとkに対してと書いてあるので、2変数はちがうんだろうなとおもう。