Parameterized Algorithms

Parameterized Algorithms

Introduction

頂点被覆

  • k人だけ消して競合を防ぐ→大きさのkの頂点被覆
  • NP完全
  • n=1000, k≦10
  • 総当り
    • 2^1000≒10^301
    • $$ {n \choose k} $$ {1000 c 10}≒10^23
    • ばか
  • 観察1
    • ぼっちは消さなくて良い
    • k人超過と競合する人は必ず消す
      • そうでないと,その人の近傍を全て消す→k人超消すことになる
    • 各頂点の次数∈[1,k]になる
    • 辺数>k^2 →無理
    • $$ {2k^2 \choose k} $$
  • 観察2
    • 次数1の頂点vがある→端点wを被覆に入れるのが最適
    • $$ {k^2 \choose k} $$
  • Kernelization(2/9章)
    • 簡単な観察で探索空間を減らす
  • さらなる観察
    • 各辺の少なくとも一方の点を被覆に入れる必要がある
      • 再帰: 2分岐,k深さ
    • 再帰時間O(n+m)
      • さっきの前処理でm≦nk/2
    • 総計算時間 = $$ O(2^k \cdot nk) $$

FPT vs. XP

  • O(2^k kn)もO(n^k)もkが定数なら多項式時間…でも大きく違う
  • FPT: $$ f(k) \cdot n^c $$
  • XP: $$ f(k) \cdot n^{g(k)} $$

頂点彩色

  • k≧3ならNP完全
    • 3彩色でさえも!
  • P=NPでなければ,XPもFPTも無い
  • 万能では無いンゴ

クリーク

  • 警備員はk人未満なら力で対処できる
  • 愚直XP
    • 候補数 = $$ {n \choose k} $$
    • O(k^2)時間で判定
  • FPT?
    • 無さそう
    • NP完全性からXPがあるけど,FPTがないっていうのは難しい
  • W[1]困難性(続きは13章)
  • タイトな下限
    • CNF-SATの困難性に関する適当な仮定のもと
    • $$ f(k) \cdot n^{o(k)} $$時間アルゴリズムは存在しない
  • 愚直な$$ O(n^k k^2) $$がほぼ最適
  • 違う設定
    • 友達がΔ=20人
    • $$ O(2^\Delta \cdot \Delta^2 \cdot n) $$
  • Objective & Measure
    • kはObjective: 入力に与えられる
    • ΔはMeasure: 明白に与えられない入力に関するパラメータ

定義

  • Parameterized Problem
    • 言語 $$ L \subseteq \Sigma^* \times \mathbb{N} $$
    • $$ (x, k) \in \Sigma^* \times \mathbb{N} $$について
    • $$k$$はparameterと呼ばれる
  • Fixed-Parameter Tractable (FPT)
    • 以下が存在する
      • アルゴリズム$$ \mathcal{A} $$
      • 計算可能関数$$ f: \mathbb{N} \rightarrow \mathbb{N} $$
      • 定数c
    • 入力 $$ (x, k) \in \Sigma^* \times \mathbb{N} $$に対し,
    • $$ \mathcal{A} $$は$$ (x, k) \in L $$かを
    • 時間$$ f(k) \cdot |(x,k)|^c $$で判定する
      • (x,k)のサイズ…|x|+k
      • fは非減少
  • Slice-Wise Polynomial (XP)
    • 上のcがg(k)に変わる

Chapter 2. Kernelization

Max-SAT

  • n変数,m節
  • k節を充足できるか?
  • 定理
    高々k変数,2k節のkernelにできる
    
  • 証明
    後で
    
  • q-expansion
  • Expansion Lemma

Kernels based on linear programming

頂点被覆

  • LP緩和
  • $$ \mathrm{minimize} \quad \sum_{v \in V} x_v $$
  • $$ \mathrm{subject to} $$
    • $$ x_u + x_v \geq 1 $$
    • $$ 0 \leq x_v \leq 1 $$
  • $$ V_0, V_{1/2}, V_1 $$: $$x_v$$が<1/2,=1/2,>1/2の頂点集合
  • Nemhauser-Trotter Theorem
    • $$ V_1 \subseteq S \subseteq V_1 \cup V_{1/2} $$
  • 帰着
    1. LPを解く
    2. if $$ \sum x_v > k $$ then NO
    3. otherwise
      1. Gから$$ V_0 \cup V_1 $$を削除
      2. $$ k \leftarrow k-|V_1| $$
  • 定理
    高々$$2k$$頂点のkernelにできる
    
  • Nemhauser-Trotter の証明
    • $$ S=(S^* \setminus V_0) \cup V_1 $$とする
    • Sが頂点被覆: 簡単
    • |S|=|S*|: 背理法
  • 命題
    • LPVC(G)はhalf-integral 最適解を持つ
    • 各変数が0,1/2,1のどれか
    • $$ O(m \sqrt{n}) $$時間

Sunflower lemma

  • A sunflower with k petals and a core Y は集合$$ S_1, \ldots, S_k $$で
    • S_iが互いに素
    • S_i \ Y は非空
  • Sunflower (Erdős-Rado) Lemma

Chapter 3 有界探索木 Bounded search trees

  • $$I$$: インスタンス
  • $$ I_1, \ldots, I_\ell $$に分割
    1. $$I$$の答えに辿り着く
    2. $$\ell \leq \mu(I)$$
    3. $$ \mu(I_i) \leq \mu(I) - c $$

頂点被覆

  • $$ O(n \sqrt{m} + 4^k k^{O(1)}) $$
    • サイズ2kのカーネルにできるので
  • もっと頭良い観察
    • 頂点被覆はvかN(v)を含む
    • $$ \Delta \leq 1 $$なら自明
  • こんな手法
    1. 最大次数の頂点を選択
    2. $$ \deg(v) \leq 1 $$ なら自明に解く
    3. 2通りに分岐
      1. vを解に追加: $$ (G-v, k-1) $$
      2. N(v)を解に追加: $$ (G-N(v), k-|N(v)|) $$
  • (葉の数)<=(葉以外の数)-1なので,(葉の数)を抑えるよ!
  • $$ T(i) = $$
    • $$ T(i-1) + T(i-2) $$ if $$ i \geq 2 $$
      • i-2な理由: 次数が2以上だから
      • 1 otherwise
  • フィボナッチ数なので,$$ T(k) \leq 1.6181^k $$
  • 全体の計算時間 $$ O(n \sqrt{m} + 1.6181^k k^{O(1)}) $$
  • 次数2でも自明(多項式時間)
    • 孤立点/線/閉路,だけだから
  • i-2がi-3になる→ $$ 1.4656^k $$

漸化式の解き方

  • 分枝ベクトル$$ (d_1, \ldots, d_p) $$
  • $$ T(k) = \sum_{1 \leq i \leq p} T(k-d_i) $$
  • $$ P(\lambda) = \lambda^d - \sum_{1 \leq i \leq p} \lambda^{d-d_p} $$
  • これのゼロ点を求める→$$ \lambda_0 $$
  • 普通

帰還(feedback)頂点集合

  • 色んな(でも割と自明な)Reduction
  1. self-loopは消す
  2. 多重辺は高々重み2
    • u->v->uだけ考えればOK
  3. 次数1は消す
  4. 次数2は自分を消して端点を繋ぐ
    • 利点がないから
  • 次数は3以上(今回大事)
  • 霊感
    • 森に超高次数は無さそう
  • 補題
    • 次数順にソート
    • 上から3k個の内1つは解に含まれる
      • そうでないと矛盾する
  • アルゴリズム
    • Reductionしまくる
    • 次数top-3kから頂点vを選ぶ
    • $$ (G-v, k-1) $$に分岐

頂点被覆のLP緩和

  • $$ f(k - \mathrm{vc}^*(G)) n^{O(1)} $$時間
    • vc*(G)はLP緩和の最小値
    • ギャップが小さいと嬉しい

最近接文字列(closest string)

Chapter 5: Randomized methods in parameterized algorithms

  • 道具: color coding, random separation, chromatic coding

フィードバック頂点集合の簡単な乱択アルゴリズム

  • 確率$$ (f(k)n^{O(1)})^{-1} $$で成功して欲しい
  • $$ f(k)n^{O(1)} $$回反復すれば定数確率で成功
  • k頂点取り除いて閉路を無くせるか?
  • 次数3以上として良い
    • 1は意味が無い
    • 2はu-v-wをu-wに変えられる
  • 補題: Xがfeedback頂点集合
    • G中の半分の辺は端点がXに含まれる
  • アルゴリズム
  1. 削除/縮約→次数≧3
  2. k回繰り返し
    1. 辺を一様に選択
    2. 端点を一様に選択し,削除
  • 成功確率 $$ 1/4^k $$
  • 逆数回繰り返せばOK

Color coding: 最長経路

  • 問題: k頂点の経路があるか?
  • 各頂点をk色に塗る(無作為)
  • あるk頂点が相異なるk色で塗られる確率 $$ \frac{k!}{k^k} \geq e^{-k} $$
  • どっかから初めて[今いる頂点][つかった色集合]でDP…$$ O(2^k n^{O(1)}) $$
  • 総計算量: $$ O((2e)^k n^{O(1)}) $$
    • あとで改善

Random separation: Subgraph isomorphism

  • GからHと同型な部分グラフを見つけたい
  • パラメータ: $$ k=|V(H)|, d=\Delta(G) $$
  • 頂点を確率1/2で無作為に削る
  • 運が良い時: H(に対応する部分)の頂点が取り除かれず,近傍が取り除かれた
    • 連結成分が丁度k頂点になる
  • その確率: $$ \geq 2^{-dk} $$
  • Gから削った後のグラフの各連結成分との同型判定: $$ k! $$
    • NOTE: $$ {n \choose k} $$ではない
  • 総計算量: $$ O(2^{dk}k!n^{O(1)}) $$

Divide and Color: 最長経路

  • Color coding + 分割統治
  • 各頂点を赤/青に塗る
    • 最初半分が赤,最後半分が青だと嬉しい
    • 赤部分と青部分で再帰して,それぞれ長さk/2の経路を求める
    • 経路の始点・終点の集合$$ n^2 $$だけ求めて上手く併合$$ n^4 $$時間
  • 成功確率$$ 1/2^{O(k \log k)} $$
  • 深さ1: $$ k=8, 1/2^8 $$
    • 深さ2: $$ k=4, 1/2^4 $$
      • 深さ3: $$ k=2, 1/2^2 $$ …
      • 深さ3: $$ k=2, 1/2^2 $$ …
    • 深さ2: $$ k=4, 1/2^4 $$
      • 深さ3: $$ k=2, 1/2^2 $$ …
      • 深さ3: $$ k=2, 1/2^2 $$ …
  • 時間$$ O(2^{O(k \log k)}n^{O(1)}) $$
    • 悪くなった!
  • 改善版
  1. $$ \mathsf{Rec}(G, d): $$
    1. 以下を$$ 2^d \log 4k $$回繰り返し
      1. Gの頂点を2色に塗る
      2. $$ \mathsf{Rec}(G_{r}, d/2) $$
      3. $$ \mathsf{Rec}(G_{b}, d/2) $$
      4. 結果を併合,答えを更新
  • ある再帰での塗り分けが死ぬ確率$$ \left( 1-\frac{1}{2^d} \right)^{2^d \log 4k} \leq \frac{1}{2k} $$
  • 全部で死ぬ確率 ≦1/2
    • TOOD: 要復習
  • 計算時間: $$ O(4^{k+o(k)}n^{O(1)}) $$

Chromatic Coding

  • 補題
    • 辺数kのグラフの頂点を$$ \sqrt{8k} $$色で塗る
    • 彩色が妥当な確率は≧$$ 2^{-\sqrt{k/2}} $$
  • $$ d\mathsf{-Clustering} $$
  • 与えられたグラフに辺挿入/削除を高々k回繰り返しd-clustering graphにできるか?
  • d-clustering graph
    • 連結成分数がd,各連結成分がクリーク
  • 同じ色の辺を編集しないとする
  • 運が良い時: 解の辺(k本)の端点の色が違う…補題の確率

脱乱択

  • 答えが何でも良いような複数の彩色を決定的に使う
  • color codingの場合
  • $$(n,k)$$-完全ハッシュ族
    • n要素からどのk要素を取ってきても色が相異なるようなハッシュが存在する
  • 分割統治の場合
    • $$(n,k)$$-universal set

Chapter 7: Treewidth

木分解の性質

  • AとBがseparation
    • $$ A \cup B = V $$
    • $$ A \setminus B - B \setminus A $$間に辺が無い
    • $$ A \cap B $$…separator
      • AからBに行くにはA∩Bを通らなければならないから
  • 補題 7.3
    • 木分解中のバッグ$$ X_a, X_b $$
    • A…X_aから下の頂点集合
    • B…X_bから下の頂点集合
    • (A,B)はGのseparation,すなわちseparatorは$$ A \cap B = X_a \cap X_b $$
      • AからBへの辺はあるとしたら,Xa--Xbになってる
  • KEY: 「バッグを除くと元のグラフで非連結になる」

Nice 木分解

  • 根は$$ X_r = \emptyset $$
  • 葉は$$ X = \emptyset $$
  • 非葉は以下の3種類
  • Introduce: $$ X_t = X_{t'}+v $$ ― $$ X_{t'} $$
  • Forget: $$ X_t = X_{t'}-v $$ ― $$ X_{t'} $$
  • Join: $$ X_t=X_{t_1}=X_{t_2} $$が$$ X_{t_1}, X_{t_2} $$に分岐
  • 計算時間: $$ O(k|V(G)|) $$
  • サイズ: $$ k^2 \cdot \max(|V(T)|, |V(G)|) $$

木分解上のDP

  • 重み付き独立集合
    • $$ O(2^k \cdot k^{O(1)} \cdot n) $$時間
    • 何を保存するか?
    • $$ c[t,S] := $$ 独立集合であって,$$X_t$$に関して丁度Sだけを含む($$\hat{S} \cap X_t = S$$)もののなかで最大の重み
    • Sが独立集合かは木幅で考えてちょっと頑張る
    • $$ 2^k k^{O(1)} n $$
  • Courcelle's theorem
    • 一般的に解けるかの話

木分解の計算

  • 時間$$ k^{O(k)}n $$で走り
    • 木幅k以下の木分解を出力 or
    • $$ \mathrm{tw}(G) > k $$としてreject
  • 定理 7.23
    • 時間$$ O(8^k k^2 n^2) $$
      • 木幅4k+4以下 or
      • reject
  • decompose(W,S)…難しい,その内読む

6章 その他

部分集合上の動的計画法

集合被覆

  • Fからk個選んでUを被覆できますか?
  • $$ 2^{|U|}(|U|+|\mathcal{F}|)^{O(1)} $$時間
  • $$ T[X,j] := $$ $$ \{F_1, \ldots, F_j\} $$の部分集合で$$X \subseteq U$$を被覆する最小サイズ
  • 答え…$$ T[U, |\mathcal{F}|] $$

Steiner木

  • $$ 3^{|T|}n^{O(1)} $$時間
  • 都合上,(ターミナルの次数)=1
    • 新しい頂点を生やせば良い
  • $$ T[S,v] := $$ SのSteiner木でvを端点として持つ
  • $$ \min_{u \in V, X \subset S} ( T[X,u] + T[S \setminus X,u] + d(v,u) ) $$
  • Sを二分割,uを端点とするSteiner木を計算,u-vをくっつける

整数線形計画

  • Ax≦bを満たすxがあるか判定できれば,最適解は二分探索でできる
    • 範囲をちゃんと抑えれば

Imbalance 問題

  • グラフの頂点を順序付ける
  • |(入次数)-(出次数)|の最悪値を最小化
  • 大きさkの頂点被覆Xも入力でもらえる設定を考える
  • I=V-Xは独立集合
  • Xをとりあえず順序付け(k!通り)
  • Iをどうする?
    • L0<π(u1)<L1<π(u2)<L2<…<π(uk)
    • Iの分割L0,L1,…,Lk
      • 分割内の頂点順はどうでも良い(独立集合だから)
    • ILPで解くよ
      • よく分からん,各頂点をどこに割り当てるか,みたいな変数を持つ
最終更新:2016年01月08日 14:12