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

https://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズム入門 岩田 陽一

• 何の指数？
  • 巡回セールスマン問題 $e^{n\log n}\to 2^n$
  • 最大クリーク問題 $2^{V}V\to 2^{\sqrt{2E}}V$
  • グラフの「幅」
    • グリッドグラフ pathwidthが小さい
• 指数の底は？
  • 半分全列挙 $2^n\to 2^{n/2}$
  • 最大独立集合問題 $2^{n}n\to 1.466^{n}n$
  • ，探索アルゴリズム 23
• FPTアルゴリズム
  • 入力サイズとは独立なパラメータ𝑘に関してのみ指数時間のアルゴリズム
  • 最小頂点被覆問題 $n^{k+1}\to 2^{k}n$
    • 有界探索木
  • カーネル
    • 多項式時間O(kn)の前処理で，問題サイズを𝑘の関数𝑓(𝑘)以下にまで小さくする手法をカーネライズと呼び，小さくなった問題をカーネルと呼ぶ
  • シュタイナー木問題 $3^{k}n{2}^{k}m$
• 包除原理
  • ハミルトンパスを多項式空間で
  • グラフ彩色問題 彩色数$k^n\to 3^n\to 2^{n}n$
  • 高速ゼータ変換
  • 畳込み
    • $(f\cdot g)(S)={\sum }_{T\subseteq S}f(T)g(S\backslash T)$
    • 集合に対するDPを高速化$3^n\to 2^n$
  • 完全マッチングの個数 完全マッチングの個数は $O(2^{n/2}$ で可能
• Color Coding
  • k-Cycle グラフに長さ𝑘の単純な閉路が含まれるか判定 $n^k\to (2e{)}^{k}m$
• Bandwidth 頂点を一列に並べ，一番長い辺の長さを最小化する $n!\to 5^n$
• Cut & Count グリッドグラフ上のシュタイナー木問題 c
• Iterative Compression グラフから𝑘点取り除いて木にできるか判定 3