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章)
-
さらなる観察
-
各辺の少なくとも一方の点を被覆に入れる必要がある
-
再帰時間O(n+m)
-
総計算時間 = $$ 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完全
-
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 $$で判定する
-
Slice-Wise Polynomial (XP)
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} $$
-
帰着
-
LPを解く
-
if $$ \sum x_v > k $$ then NO
-
otherwise
-
Gから$$ V_0 \cup V_1 $$を削除
-
$$ 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 $$で
-
Sunflower (Erdős-Rado) Lemma
Chapter 3 有界探索木 Bounded search trees
-
$$I$$: インスタンス
-
$$ I_1, \ldots, I_\ell $$に分割
-
$$I$$の答えに辿り着く
-
$$\ell \leq \mu(I)$$
-
$$ \mu(I_i) \leq \mu(I) - c $$
頂点被覆
-
$$ O(n \sqrt{m} + 4^k k^{O(1)}) $$
-
もっと頭良い観察
-
頂点被覆はvかN(v)を含む
-
$$ \Delta \leq 1 $$なら自明
-
こんな手法
-
最大次数の頂点を選択
-
$$ \deg(v) \leq 1 $$ なら自明に解く
-
2通りに分岐
-
vを解に追加: $$ (G-v, k-1) $$
-
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)頂点集合
-
self-loopは消す
-
多重辺は高々重み2
-
次数1は消す
-
次数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頂点集合
-
アルゴリズム
-
削除/縮約→次数≧3
-
k回繰り返し
-
辺を一様に選択
-
端点を一様に選択し,削除
-
成功確率 $$ 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(に対応する部分)の頂点が取り除かれず,近傍が取り除かれた
-
その確率: $$ \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)}) $$
-
改善版
-
$$ \mathsf{Rec}(G, d): $$
-
以下を$$ 2^d \log 4k $$回繰り返し
-
Gの頂点を2色に塗る
-
$$ \mathsf{Rec}(G_{r}, d/2) $$
-
$$ \mathsf{Rec}(G_{b}, d/2) $$
-
結果を併合,答えを更新
-
ある再帰での塗り分けが死ぬ確率$$ \left( 1-\frac{1}{2^d} \right)^{2^d \log 4k} \leq \frac{1}{2k} $$
-
全部で死ぬ確率 ≦1/2
-
計算時間: $$ 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
-
同じ色の辺を編集しないとする
-
運が良い時: 解の辺(k本)の端点の色が違う…補題の確率
脱乱択
-
答えが何でも良いような複数の彩色を決定的に使う
-
color codingの場合
-
$$(n,k)$$-完全ハッシュ族
-
n要素からどのk要素を取ってきても色が相異なるようなハッシュが存在する
-
分割統治の場合
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
-
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