指数時間アルゴリズム入門

https://gyazo.com/977ede9fb56afe8240c8f2b43c72179e

何の指数？

最大クリーク問題 $ 2^V V → 2^{\sqrt{2E}} V

グラフの「幅」

指数の底は？

半分全列挙 $ 2^n→2^{n/2}

，探索アルゴリズム 23

入力サイズとは独立なパラメータ𝑘に関してのみ指数時間のアルゴリズム

カーネル

多項式時間O(kn)の前処理で，問題サイズを𝑘の関数𝑓(𝑘)以下にまで小さくする手法をカーネライズと呼び，小さくなった問題をカーネルと呼ぶ

$ (f\cdot g)(S) = \sum_{T \subseteq S} f(T) g(S \backslash T)

集合に対するDPを高速化$ 3^𝑛 → 2^n

k-Cycle グラフに長さ𝑘の単純な閉路が含まれるか判定 $ n^k → (2e)^km

Bandwidth 頂点を一列に並べ，一番長い辺の長さを最小化する $ n!→5^𝑛

Cut & Count グリッドグラフ上のシュタイナー木問題 c^w

Iterative Compression グラフから𝑘点取り除いて木にできるか判定 3^k