指数時間アルゴリズム入門 岩田 陽一

何の指数？

巡回セールスマン問題 e^{n\log n}→2^n

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

グラフの「幅」

グリッドグラフ pathwidthが小さい

指数の底は？

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

最大独立集合問題 2^n n → 1.466^n n

，探索アルゴリズム 23

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

最小頂点被覆問題 n^{k+1} → 2^kn

カーネル

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

シュタイナー木問題 3^kn2^km

ハミルトンパスを多項式空間で

グラフ彩色問題 彩色数k^n→3^n→2^nn

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

完全マッチングの個数 完全マッチングの個数は O(2^{n/2} で可能

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

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

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

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