FPTにおいては幅とパラメータが存在する。たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。 k-クリーク判定では幅に対しての組み合わせになるので二項定理からなので、を用いてのオーダーで上限を決め…

最大クリーク問題のの中身を分解して、の多項式になっていることを証明しないとダメな気がしてきた。わかった。ZPP=EXPTIMEでP≠NPのほうだ

グラフのDegeneracyをkとすると前処理後、おおまかで最大クリークが求まるな。Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフを順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。最大出次数をとする…