頂点被覆と双劣モジュラ緩和

劣モジュラ緩和による
線形時間FPTアルゴリズム
𠮷田悠一
国立情報学研究所
ELC計算量理論秋学校（９／２５）
自己紹介：𠮷田悠一
国立情報学研究所
• 情報学プリンシプル研究系特任助教
⇒ 理論計算機科学 (性質検査・ＣＳＰなど)
• ビッグデータ数理国際研究センター副センター長
• JST ERATO河原林巨大グラフプロジェクト複雑ネット
ワーク・地図グラフグループリーダ
⇒ 大規模データに対する実用的（＝高速）アルゴリズム
(株) Preferred Infrastructure 顧問
宣伝
FOCS2014でワークショップをやります。
Higher-order Fourier Analysis
October 18, 2014 (Sat.)
• Arnab Bhattacharyya - Background on higher order Fourier
analysis
• Pooya Hatami - Regularity of polynomials and linear forms
• Madhur Tulsiani - Algorithmic higher-order Fourier analysis
• Emanuele Viola - Applications to lower bounds
• Yuichi Yoshida - Applications to algebraic property testing
• Abhishek Bhowmick - Applications to coding theory
固定パラメータ容易性
• P = NPでない限り、NP困難な問題はO(nd)時間で解けない
• FPT (Fixed Parameter Tractable, 固定パラメータ容易性)
– パラメータkを導入 (例: 最適値、木幅)
– ある問題がO(f(k)nd)時間で解ける時、FPTと呼ぶ。
• 例
– 大きさkのVertex Cover: FPT (O(2k|E|)時間)
– 大きさkのIndependent Set: W[1]-完全
• FPT≠W[1]と信じられている
http://fpt.wikidot.com/
今日の内容
Half-Integrality, LP-Branching and FPT Algorithms
[Iwata-Wahlström-Yoshida, submitted]
多くの問題に対して効率的(一重の指数)なFPTアルゴリズム
を得ることが出来る統一的な手法(劣モジュラ緩和)の紹介
•
•
•
•
•
Vertex Cover
Odd Cycle Transversal
Almost 2-SAT
Multiway Cut (枝削除・頂点削除)
Unique Label Cover (枝削除・頂点削除)
• Subset Feedback Vertex Set
Problems
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Group Feedback
Vertex Set
Vertex Cover
Above LP
6
Vertex Cover (頂点被覆)
頂点集合Sが頂点被覆: G[V \ S]が空
問: Gは大きさkの頂点被覆を持つか？
1
2
3
4
5
6
7
Vertex Coverに対するFPTアルゴリズム
単純な分岐アルゴリズムでO(2km)時間で解ける。
u
k-1
u
v
v
k
u
v
k-1
Odd Cycle Transversal
頂点集合Sがodd cycle transversal: G[V \ S]が二部グラフ
問: Gは大きさkのodd cycle transversalを持つか？
既存のFPTアルゴリズム
• O(3knm)時間 [Reed-Smith-Vetta 2004]
– Iterative compression
• O(f(k)α(m, n)m)時間 [Kawarabayashi-Reed 2010]
– α: アッカーマン関数の逆関数
– f(k): 非常に大きい(二重指数ぐらい？)
• O(4k(n+m))時間 [Iwata-Oka-Yoshida 2014]
Almost 2-SAT
問: 与えられた2CNFからk個の節を削除して充足可能にせよ
(x ∨ y) ∧ (x ∨ ȳ) ∧ (y ∨ z) ∧ (ȳ)
x = true, y = false, z = true
• O(15km3)時間 [Razgon-O’sullivan 2008]
• O(4k(n+m))時間 [Iwata-Oka-Yoshida 2014]
Vertex Cover above LP
問: グラフGは大きさ(LP値 + k)の頂点被覆を持つか？
1
2
3
1
2
4
5
1
6
7
0
合計: 3.5
• O*(2.6181k) [Narayanaswamy-Raman-Ramanujan-Saurabh 2013]
– LPに基づく分枝限定法
• Odd Cycle TransversalとAlmost 2-SATはVertex Cover above LP
に(パラメータkを保存して)帰着可能
Problems
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Group Feedback
Vertex Set
Vertex Cover
Above LP
12
Multiway CutとNode Multiway Cut
ターミナルT = {t1, …, t|T|}
• 枝集合Sがmultiway cut: G-Sにおいて各ターミナルが異な
る連結成分に属する
• 頂点集合Sがnode multiway cut: G-Sにおいて各ターミナル
が異なる連結成分に属する
問: グラフGは大きさkの(node) multiway cutを持つか？
Multiway Cutに対するFPTアルゴリズム
• O*(4k^3)時間 (枝・頂点両方) [Marx 2006]
•
•
•
•
– Important separator
O*(4k)時間 (枝・頂点両方) [Chen-Liu-Lu 2009]
O(4k(n+m))時間 (頂点) [Iwata-Oka-Yoshida 2014]
O*(2k)時間 (枝) [Cygan-Pilipczuk-Pilipczuk-Wojtaszczyk 2012]
O(2k(n+m))時間 (枝) [Iwata-Wahlström-Yoshida 2014]
Multiway Cut above LP
問: 大きさ(LP値 + k)のmultiway cutが存在するか？
0.5
0.5
0.5
0.5
0.5
0.5
合計3.5
0.5
• O*(4k) [Cygan-Pilipczuk-Pilipczuk-Wojtaszczyk 2012]
– LPに基づく分枝限定法
• OPT ≤ 2LP
⇒ O*(4OPT-LP) = O(2OPT)
⇒ (Edge) Multiway Cutを改善
LPに基づく分枝限定法
LPに基づく分枝限定法
Vertex Cover Above LPとMultiway Cut Above LPに用いられた
半整数性と固定可能性を利用
• LP解で値が全て{0, 1/2, 1}なものが存在（し求まる）
• LP解のうち整数部分を最適値を上げることなく固定する
ことが出来る。
17
頂点被覆に対するLP緩和
xv : 頂点vが頂点被覆に含まれるか否か
minimize Σv∈V xv
subject to xu + xv ≥ 1 (uv ∈ E)
0 ≤ xv ≤ 1 (v ∈ V)
[Nemhauser-Trotter 1975]
上記LPは半整数性と{0, 1}への固定可能性を持つ
頂点被覆に対するLP緩和
0
0
0
0
0
0
1
2
0
0
0
0
1
0
0
0
0
LPを利用した分岐(Vertex Cover above LP)
b =初期状態のLP値 + k
if LP値 > b then Noを出力
整数の変数を固定
if 全ての変数が整数 then 解を出力
半整数の変数xvを選択
if LP値を変えずにxvを0か1に固定可能 then 固定して再帰
else xv = 0とxv = 1の二通りに分岐
各分岐でLP値が1/2増加する
探索木のサイズ＝22k = 4k
⇒ O*(4k)時間アルゴリズム
Node Multiway Cutに対するLP緩和
xv: vがmultiway cutに含まれるか否か
minimizes Σv∈V xv
subject to Σv∈P xv ≥ 1 (任意のターミナル間のパスP)
0 ≤ xv ≤ 1 (v ∈ V)
指数個数の制約があるが、多項式時間の分離オラクルが作
れるので、多項式時間で解ける。
半整数性 [Garg-Vazirani-Yannakakis 2004]
固定可能性 [Guillemot 2011]
• 値1 ⇒ 固定可能
• ターミナルtから値0の頂点を辿って辿れる頂点集合U(t)
⇒ 値0に固定可能
LP relaxation of Node Multiway Cut
t4
0
1
t1
0
1/2
1/2
0
1
0
1/2
t3
1/2
1
1
0
t2
22
LPを利用した分岐(Multiway Cut above LP)
b = 初期状態のLP値 + k
if LP値 > b then Noを出力
1を取る変数と全てのtに対してU(t)を固定
if 全ての変数が整数 then 解を出力
適当なtに対してU(t)に隣接する半整数の変数xvを選択
if LP値を変えずにxvを0か1に固定可能 then 固定して再帰
else xv = 0とxv = 1の二通りに分岐
各分岐でLP値が1/2増加する
探索木のサイズ＝22k = 4k
⇒ O*(4k)時間アルゴリズム
劣モジュラ緩和
離散緩和
• 半整数かつ固定可能なLP緩和を考えるのは非常に大変
• 代わりに定義域を拡張した離散的な緩和を考える。
D: 元の定義域(整数)
D’: 拡張された定義域(D ⊆ D’) (整数 + 分数)
元の目的関数f: DV→ℤ+ を緩和してf’: D’V→ℤ+/c を作る
– 任意のx∈DVに対してf’(x) = f(x) (一貫性)
– f’はxv = iの様に変数を固定しても最小化可能
– f’の最適解x*においてvが整数ならば、vを固定しても
最適値は増加しない (固定可能性)
離散緩和に基づくFPTアルゴリズム
関数f: DV→ℤ+が一貫、最小化可能、固定可能な離散緩和
f’:D’V→ℤ+/cを持つ
⇒ fはO*(|D|c (min f – min f’))時間で最小化可能
証明
緩和問題を解き、分数の変数vを選ぶ。
もしvが緩和解を変えずに固定出来るなら固定する。
そうでなければ|D|通りに分岐する。
各分岐で1/cだけ緩和解が増加するので、探索木のサイズは
|D|c(min f – min f’)。
離散緩和と劣モジュラ性
一貫、最小化可能、固定可能な離散緩和f’をどうやって見
つける？
f’が(広い意味で)劣モジュラになるようにすれば良い！
• 劣モジュラ性から最小化・固定可能性が簡単に言える
• 多くの問題が劣モジュラ緩和を持つ
劣モジュラ性
集合関数f: 2V → ℝが劣モジュラ：
任意のS, T⊆Vに対して
f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T)
例：
• グラフのカット (無向、有向、ハイパーグラフ)
• マトロイドのランク関数
• Coverage Function
任意の劣モジュラ関数は|V|の多項式時間で最小化可能(関
数オラクルで与えられるとする)
[Iwata-Fleischer-Fujishige 2001] [Schrijver 2000]
（一般化された）劣モジュラ性
f: {0, 1}V → ℝが劣モジュラ：
任意のx, y ∈ {0, 1}Vに対して
f(x) + f(y) ≥ f(x ∨ y) + f(x ∧ y)
要素ごとに演算
一般の(有限)定義域Dに拡張
f: DV → ℝが⊔, ⊓: D2 → Dに関して劣モジュラ：
任意のx, y ∈ DVに対して
f(x) + f(y) ≥ f(x ⊔ y) + f(x ⊓ y)
双劣モジュラ関数
双劣モジュラ
• D = {-1, 0, 1}
⊔
0
1
⊓
-1
0
1
-1 -1 -1
0
-1 -1
0
0
0
-1
0
1
0
0
0
0
1
0
1
1
1
0
0
1
-1
1
-1
0
• 例: Δマトロイドのランク関数
• 任意の双劣モジュラ関数は多項式時間で最小化可能
[Fujishige-Iwata 2005]
k劣モジュラ関数
k劣モジュラ
• D = {0, 1, 2, …, k}
⊔
0
i
j
⊓
0
i
j
0
0
i
j
0
0
0
0
i
i
i
0
i
0
i
0
j
j
0
j
j
0
0
j
1
…
2
k
0
• 双劣モジュラの一般化 (双劣モジュラはk = 2)
• 多項式時間の最小化アルゴリズムは知られていない
– 定数項数のk劣モジュラ関数(の和)はLPで最小化可能
Problems
双劣モジュラ緩和
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Group Feedback
Vertex Set
Vertex Cover
Above LP
32
頂点被覆と双劣モジュラ緩和
頂点被覆
• 定義域D = {0, 1}
• 目的関数: minimize Σv∈E xv + M × Σuv∈E max(0, 1 – xu – xv)
(M: 十分大きな数)
注意: f(x, y) = max(0, 1 – x – y)は劣モジュラではない
– f(1, 0) + f(0, 1) < f(1, 1) + f(0, 0)
頂点被覆と双劣モジュラ緩和
• 離散緩和された頂点被覆
– D’ = {0, 1/2, 1}
• f’(x, y) = max(0, 1 – x – y)は⊔, ⊓に関して双劣モジュラ！
– f’(1 ⊔ 0, 0 ⊔ 1) = f’(1 ⊓ 0, 0 ⊓ 1) = f’(1/2, 1/2) = 0
⇒ Σv∈E xv + M × Σuv∈E f’(xu, xv) も双劣モジュラ
⊔
0
0
0
1/
2
1
0
1/
1/
2
0
1/
2
1
1
1/
2
1
1
⊓
0
0
0
1/
2
1
1/
2
1/
1/
2
1/
2
1/
2
1/
1
0
1/
2
1/
2
1
1
½
双劣モジュラ関数の固定可能性
補題
双劣モジュラ関数はD = {0, 1}のとき固定可能
証明
x ○ y = x ⊔ (x ⊔ y)とする。
• y∈D ⇒x○y∈D
• x, y ∈ D ⇒ x ○ y = x
• x ∈ D’V, y ∈ DV
⇒ x ○ y ∈ DV かつ各xi ∈ Dに対して(x ○ y)i = xi
双劣モジュラ関数の固定可能性
補題
双劣モジュラ関数はD = {0, 1}の時、固定可能
証明
x* = argmin f’, y* = argmin fとする。
x* ○ y*がfのminimizerであることを示す。
○を展開
f(x* ○ y*) = f’(x* ○ y*)
≤ f’(x* ⊔ (x* ⊔ y*)) + f’(x* ⊓ (x* ⊔ y*)) – f’(x*)
≤ f’(x* ⊔ y*)
≤ f’(x* ⊔ y*) + f’(x* ⊓ y*) – f’(x*)
≤ f’(y*) = f(y*)
最小値
頂点被覆と双劣モジュラ緩和
大きさkの頂点被覆はO*(4k-min f’)時間で見つかる。
min f’はLP緩和の最適値と一致
• LP ≥ OPT/2より頂点被覆はO*(2k)時間で解ける。
• Vertex Cover above LPがO*(4k)時間で解ける。
Binary関数と双劣モジュラ緩和
• 任意のBinary関数{0, 1}2 → ℤ+は、双劣モジュラ関数{0, 1/2,
1}2 →ℤ+/2に緩和可能。
0
1
0
a
b
1
c
d
=a
1
0
0
0
+b
0
1
0
0
+c
0
0
1
0
+d
0
0
0
1
• Binary関数の和で書ける関数fはO*(4min f)時間で最小化可
能。
– Vertex Cover, Odd Cycle Transversal, Almost 2-SAT
Problems
双劣モジュラ緩和
k劣モジュラ緩和
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Group Feedback
Vertex Set
Vertex Cover
Above LP
39
Multiway Cutとk劣モジュラ緩和
Multiway Cut (T = {t1, …, t|T|})
• D = {1, …, |T|}
• Minimize Σuv∈E [xu ≠ xv] subject to xti = i.
– [1 ≠ 0]’ + [0 ≠ 2]’ ≥ [1 ≠ 2]’ + [0 ≠ 0]’
|T|
0
離散緩和されたMultiway Cut
• D’ = {0, 1, …, |T|}
0 (x = y)
• [x ≠ y]’ = 1/2 (x = 0 xor y = 0)
1 (otherwise)
• [x ≠ y]’ は|T|劣モジュラ！
…
2
1
⊔
0
i
j
⊓
0
i
j
0
0
i
j
0
0
0
0
i
i
i
0
i
0
i
0
j
j
0
j
j
0
0
j
Multiway Cutとk劣モジュラ緩和
t3
3
1
1
2
1
t1
0
2
t2
双劣モジュラ関数の固定可能性
補題
k劣モジュラ関数はD = {1, 2, …, k}の時、固定可能
証明
双劣モジュラの時と同様。
x ○ y = x⊔(x⊔y)とする。
定数項数のk劣モジュラ関数の和はLPで最小化可能。
• Multiway CutはO*(2k)時間で解ける。
• Multiway Cut above LPがO*(4k)時間で解ける。
Problems
双劣モジュラ緩和
k劣モジュラ緩和
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Unique Label
Cover
Group Feedback
Vertex Set
Vertex Cover
Above LP
43
Unique Label Cover
入力: ラベル集合Σ, 有向グラフG = (V, E), 置換{πe: Σ→Σ}
目的: 充足されない制約が高々k個の割り当てを求める
制約uv ∈ Eが割当φ: V → Σで充足 ⇔ π(φ(u)) = φ(v)
パラメータ: |Σ|とk
• Unique Games Conjectureの核
となる問題
http://en.wikipedia.org/wiki/Unique_games_conjecture
• O*(|Σ|O(k^2)) [Chitnis-Cygan-Hajiaghayi-Pilipczuk-Pilipczuk 2012]
– ランダム縮約
– パラメータがkのみだとW[1]困難
Unary関数のk劣モジュラ緩和
• 任意のunary関数f: D → ℤ+はk劣モジュラ緩和を持つ
f(x)
(x ∈ D)
f’(x) =
(f(d1) + f(d2)) / 2 (x = 0)
(d1 := argminx∈D f(x), d2 := argminx∈D-d1 f(x))
• Hard制約fi(x) = [x ≠ i] × ∞はk劣モジュラ関数で表現可能
0 (x = i)
f’i(x) = M / 2 (x = 0)
M (otherwise)
(M: 十分大きな値)
Binary関数のk劣モジュラ緩和
• 任意の置換πに対してfπ(x, y) := [x ≠ π(y)] はk劣モジュラ緩
和可能
f’π(x, y) =
0 (x = π(y) or x = y = 0)
1/2 (x = 0 xor y = 0)
1 (otherwise)
• 任意のa, bに対して fa∨b(x, y) := [x ≠ a ∧ y ≠ b]はk劣モジュラ
緩和可能
f’a∨b(x, y) =
0 (x = a or y = b or x = y = 0)
1/2 (x = 0 xor y = 0)
1 (otherwise)
Unique Label Coverとk劣モジュラ緩和
Unique Label Cover
• D = {1, 2, …, |Σ|}
• Minimize Σuv∈E fπuv (xu, xv)
⇒ |Σ|劣モジュラ緩和Σuv∈E f’πuv (xu, xv)を持つ
⇒ Unique Label CoverはO*(|Σ|2k)時間で解ける
Problems
双劣モジュラ緩和
k劣モジュラ緩和
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Unique Label
Cover
Group Feedback
Vertex Set
Vertex Cover
Above LP
48
(有限) 値付き制約充足問題 (VCSP)
• 言語Γ
– 定義域: D
– F: コスト関数f: Dar(f)→ℚ+の集合
• VCSP(Γ)の入力I
– 変数集合V = {x1, …, xn}
– 目的関数fI
fI = Σi wi fi(xi) (wi∈ℚ+, fi∈F, xi ∈ Var(fi))
• 目的関数fIを最小化する割当φ: V→Dを見つけたい
VCSPの例
最小カット
• D = {0, 1}
f≠(x, y) = [x ≠ y]
• F = f0(x) = [x ≠ 0] × ∞
f1(x) = [x ≠ 1] × ∞
⇒ 多項式時間で解ける
最大カット
• D = {0, 1}
• F = {f=(x, y) = [x = y], f0, f1}
⇒ NP困難
VCSPの特徴付け
多項式時間で解けるVCSP(Γ)の特徴付け [Thapper-Zivny 2013]
• もしΓがバイナリ冪等対称fractional polymorphismを持て
ば、VCSP(Γ)は(LPで)多項式時間で解ける
• そうでなければVCSP(Γ)はNP困難
• バイナリfractional polymorphism 𝒟
– 𝒟: バイナリ演算D2→Dの分布
– 任意のf ∈ Fに対してf(x) + f(y) ≥ E○~𝒟[f(x ○ y)]
(例: 劣モジュラ ⇔ 𝒟 = ⊔ × 1/2 + ⊓ × 1/2)
• 冪等: x ○ x = x (∀○ ∈ supp(𝒟))
• 対称: x ○ y = y ○ x (∀○ ∈ supp(𝒟))
Node Multiway Cut
Node Multiway Cut (T = {t1, …, th})
• D = {1, …, h, C} (C = その頂点を取り除く)
• minimize Σv∈V f(xv) + M × Σuv∈E g(xu, xv)
s.t. xti = i
f
g
i
j
C
i
0
i
0
1
0
j
0
j
1
0
0
C
1
C
0
0
0
• k劣モジュラ緩和できないので他のmultimorphismを使う。
Node Multiway Cutの劣モジュラ緩和
Node Multiway Cut (T = {t1, …, th})
• D = {1, …, h, C, 0, 1’, …, h’}
• minimize Σv∈V f(xv) + M × Σuv∈E g(xu, xv)
s.t. xti = I
f
g
i
j
C i' j’ 0
⊔ i
j
C i' j’ 0
⊓ i
j
C i' j’ 0
i
i’
i
i
i
0 i’ i’ 0 0
j’ j’
j
j
j
0
j
i
0
i
0 1 0 0 ½ ½
i
i
0 i’
j
0
j
1 0 0 ½ 0 ½
j
0
j
j’ 0 j’ 0
C 1
C 0 0 0 0 0 0
C i’ j’ C C C C
C i’ j’ C i’ j’ 0
i’ ½
i’ 0 ½ 0 0 0 0
i’
j’ C i’ C i’
i’ i’ 0 i’ i’ 0 0
j’ ½
j’ ½ 0 0 0 0 0
j’ i’
j
C C j’ j’
j’ 0 j’ j’ 0 j’ 0
0 0
0 ½ ½ 0 0 0 0
0
j
C i’ j’ 0
0 0 0 0 0 0 0
i
i
t4
4
C
t1
1
1’
4’
0
C
3
3’
2’
C
C
2
t2
t3
Node Multiway Cutの劣モジュラ緩和
• バイナリ冪等対称fractional polymorphismが存在するので
最小化可能
• 固定可能性の証明は双劣モジュラの時と同じ
– x ○ y = x ⊔ (x ⊔ y)を考えれば良い
⇒ Node multiway cutはO*(4k)時間で解ける。
Subset Feedback Set
入力: G = (V, E), T ⊆ E
S ⊆ Vが(Tに対する)subset FVS: Tを通る全ての単純閉路がSの
頂点を通る
問: 大きさkのsubset FVSは存在するか？
• O*(2O(klogk))時間 [Cygan-Pilipczuk-Pilipczuk-Wojtaszczyk 2012]
• O*(4k)時間 [Iwata-Wahlström-Yoshida 2014]
Group FVS
入力: 群(Σ, ○), 有向グラフG = (V, E), φ: E → Σ (φ(uv) = φ(vu)-1)
S ⊆ VがGroup FVS: 全ての非０サイクルがSの頂点を通る
問: 大きさkのGroup FVSは存在するか？
多くの問題がGroup FVSに帰着できる
(1,0)
(0,0)
(0,0)
(0,1)
(0,0)
(0,0)
(0,0)
(0,0) (0,0)
(0,0)
Subset FVSはℤ2|S|で表現可能
オラクルモデル上のGroup FVS
帰着を考えるとΣのサイズは指数にしたい
⇒ 群はオラクルで与えられる ((a, b) ↦ a ○ b)
• O*(2O(klogk))時間 [Cygan-Pilipczuk-Pilipczuk 2012]
• O*(4k)時間 [Iwata-Wahlström-Yoshida 2014]
Problems
双劣モジュラ緩和
k劣モジュラ緩和
Vertex Cover
Multiway Cut
Unique Label
Cover
Odd Cycle
Transversal
Multiway Cut
Above LP
Subset Feedback
Vertex Set
Almost 2-SAT
Unique Label
Cover
Group Feedback
Vertex Set
Vertex Cover
Above LP
Linear-time FPT
59
極限解
y ∈ D’Vがx ∈ D’Vを支配:
• ∀i, xi ∈ D ⇒ yi = xi
• ∃i, xi ∉ D ∧ yi ∈ D
緩和問題の最適解x* ∈ D’Vが極限: x*は支配されていない
x*が極限な時、分数を整数にすると値が真に増加する。
⇒ LP解に基づく分岐で有利
k劣モジュラ関数の線形時間FPTアルゴリズム
[定理] [Iwata-Wahlström-Yoshida 2014]
関数f’: D’V → ℤ+/2をunary関数, f’π, f’a∨bのm個の和とする。
f’の極限解はO(km × min f’)時間で求められる。
⇒ Odd Cycle Transversal, Almost 2-SAT, Unique Label Coverに対
する初の線形時間FPTアルゴリズム
ネットワークの構築
極限解を求める為にネットワークを構築する
頂点
• ソースs, シンクt
• 各頂点vに対して頂点集合Xv := {vi : i ∈ D}を用意
s-tカットが合法：
各頂点vに対して高々一つのXvの頂点がs側に入る。
カットと解の対応
合法なカットと解を以下の様に対応づける
• viがs側に存在 ⇔ xv = i
• Xvが全てt側に存在 ⇔ xv = 0
各関数に対してネットワークを作成し、合法なカットのサ
イズが対応する解のコストに一致することを示す(等価性)
任意の違法な最小カットがサイズを変えずに合法化できる
ことを示す(合法化可能性)
– Xvの二点以上がs側に含まれていたら、全てt側に移動
すれば良いことを示す
Unary関数のネットワーク
f’(0) = (f(d1) + f(d2) / 2
f(d1) = 0と仮定してよい。a := f(d2)と置く。
a/2
s
d1
t
f’(i) – a/2
cost(s, xd1) = a / 2
cost(xi, t) = f’(i) – a / 2 (i ≠ d1)
Unary関数の等価性と合法化可能性
等価性
• xv = 0 ⇒ カット = a/2 = f’(0)
• xv = d1 ⇒ カット = 0 = f’(1)
• xv = i (≠ d1) ⇒ カット = a/2 + f’(i) – a/2 = f’(i)
合法化可能性
• Tv ⊆ Xv, |Tv| ≥ 2をs側の頂点とする。
少なくともカットはa/2以上なので、全てt側に移動可能
置換のネットワーク
fπ(x, y) =
0 (x = π(y) or x = y = 0)
1/2 (x = 0 xor y = 0)
1 (otherwise)
π = 1 (2 3)
s
t
cost(ui, vπ(i)) = cost(ui, vπ(i)) = 1/2
fa∨bにも同様にして構築可能
極限解の計算
• 合法化可能性より合法な最小s-tカットが得られる。
• 等価性よりこれは最適解に対応する。
極限解を得る為に以下の補題を利用
補題 [Picard, Queyranne 1980]
s-t最小カットと、s-t最大フローの残余ネットワークにおけ
るsを含む”閉じた”頂点集合には一対一対応がある。
アルゴリズム
• 合法な最小カットS ⊆ Vと対応するs-t最大フローを計算
• 残余ネットワークにおける強連結成分を計算
• while これまで見ていない強連結成分⊆V \ Sが存在
– Cを一番tail側の強連結成分とする
– もしCをs側に移動しても、合法な最小カットが得られ
るなら移動する
– そうでなければt側に留める。
• 現在の（合法な）カットに対応する解を出力
s
t
正しさ
補題
得られた合法なカットに対応する解は極限解である。
残余ネットワークにおいてsからtに行くパスは存在しない
ので、得られたカットは最小カットである。
得られた解x*が極限解でないとすると、あるy*が存在してx*
を支配する。
y*に対応する合法カットはx*よりも真にt側に存在する。
この時、強連結成分をs側に移動することが出来るので矛盾。
まとめ
• LPに基づく分岐を発想とした離散緩和を紹介
• （広義の）劣モジュラ性を利用することで
– 最小化可能性
– 固定可能性
が容易に証明可能
• 紹介していない他の問題にも応用可能
– 劣モジュラ頂点被覆
– 劣モジュラ2SAT
• 特殊な場合には最大流を使って線形時間FPTが得られる
今後の課題
• Unique Label Coverの頂点削除版は線形時間FPT?
• どのVCSPは最大流で解ける？
– 項数 ≤ 4,D = {0, 1}の場合は解決済み[Zivny-Cohen-Jeavons 2009]
– 任意のバイナリk劣モジュラ関数？
• （広義の）劣モジュラ性を越えた離散緩和？
– 有向グラフ？（例: Directed FVS, Directed Multiway Cut）
– SDPに由来する緩和？
• どのVCSPはI ⊆ DにおいてFPT時間で最小化可能？
• オラクルで与えられたk劣モジュラ関数最小化
71

Download Report