スライド 1

第4章 多分割カットと k-カット
作: 牧山幸史
これまでのあらすじ
•
•
•
•
現実で遭遇する最適化問題の多くは「NP困難」
厳密解を求めるのに、膨大な計算時間が必要
近似解ならば、求めることができるかも。
個々の問題に対する近似アルゴリズムを調査する
(第Ⅰ部):
第1章: 個数版点カバー問題
(近似率2)
第2章: 集合カバー問題
(近似率 Hn)
第3章: シュタイナー木とTSP
(近似率2と1.5)
第4章: 多分割カットと k-カット
多分割カットと k-カット(目次)
• (寄り道) 最小 s-t カット問題
• 多分割カット問題
• 最小 k-カット問題
ふじ祭り(吉祥寺)
• 北九州八幡西区吉祥寺町
• 明治37年に樹齢50年位
たったフジを植えたのがは
じまり
• フジが咲き揃った様は豪華
絢爛
• 4月下旬から5月上旬にか
けて見頃
• フジの開花期間は夜10時
までライトアップされ夜も花
見ができる
ふじ祭り(吉祥寺)
◆ 開花時期
には多くの
見物客が訪
れる
ふじ祭り(吉祥寺)
◆ ふじ祭り期間には
参道にたくさんの
店がでる
ある露店にて
フ
ァ
ミ
コ
ン
ジ
ュ
ー
ス
ぬ
い
ぐ
る
み
せ
ん
べ
い
た
わ
し
お
か
し
糸切り
1回 100円
ある露店にて
フ
ァ
ミ
コ
ン
ジ
ュ
ー
ス
ぬ
い
ぐ
る
み
せ
ん
べ
い
た
わ
し
お
か
し
糸切り
1回 100円
ちょっとした提案
店のにーちゃん
100円
100円
100円
100円 100円
目隠し
フ
ァ
ミ
コ
ン
ジ
ュ
ー
ス
ぬ
い
ぐ
る
み
せ
ん
べ
い
た
わ
し
糸切り
1回
100円
ちょっとした提案
店のにーちゃん
店のにーちゃん
450円
100円
100円
100円
100円 100円
100円
250円
10円
50円
120円
フ
ァ
ミ
コ
ン
ジ
ュ
ー
ス
ぬ
い
ぐ
る
み
せ
ん
べ
い
た
わ
し
糸切り
1本
100円
450円
10円
300円
200円
1000円
ファミコン
ちょっとした提案
店のにーちゃん
店のにーちゃん
450円
100円
250円
10円
50円
120円
フ
ァ
ミ
コ
ン
ジ
ュ
ー
ス
ぬ
い
ぐ
る
み
せ
ん
べ
い
た
わ
し
糸切り
1本
100円
450円
10円
300円
200円
1000円
ファミコン
ちょっとした提案
店のにーちゃん
450円
250円
700円
370円
100円
10円
50円
120円
450円
610円
10円
300円
200円
1000円
ファミコン
430円
1000円
最小
最小 s-t カット問題
• 辺に重みを持つ連結なグラフ G が与えられ、2つの
頂点 s, t が指定されたとき、次の性質を持つ辺集
合のうちで、重みの総和が最小となるものを見つけ
よ:
• その辺集合に属する辺をすべて取り除くと、グラフ
G は s を含む部分グラフと t を含む部分グラフとに
分割される。
• このような辺集合を s-t カット という。
最小 s-t カット問題
s
店のにーちゃん
450円
100円
250円
10円
50円
120円
450円
300円
250
100
10
50
120
10円
200円
450
10
300
200
1000円
ファミコン
450
1000
t
最小 s-t カット問題
s
店のにーちゃん
450円
100円
250円
10円
50円
120円
450
100
450円
10
50
120
10円
300円
200円
250
10
300
200
1000円
ファミコン
450
1000
610
(100+50+10+450)
t
最小 s-t カット問題
s
店のにーちゃん
450円
100円
250円
10円
50円
120円
450
100
450円
120
300円
1000円
ファミコン
10
50
10円
200円
250
450
10
300
200
最小
370
(100+10+10+250)
1000
t
最小 s-t カット問題
• 一般のグラフが与えられたとき、最小 s-t カットを求
める多項式時間アルゴリズムは存在するか?
• 答え: 存在する
• なぜならば、最大フローを求める多項式時間アルゴ
リズム(Goldberg-Tarjan Algorithm)が存在する
からである。
最大フロー最小カット定理 (maxflow-mincut thm.)
重み付きグラフ(ネットワーク)の最大フローと最小カット
の値は一致する。
ネットワークの最大フロー
• ネットワークの重みを、単
位時間にその辺へ流すこ
とのできる最大の水量と
みなす。
• このとき、頂点 s から t
へ流すことのできる最大
の水量を最大フローとい
う。
s
450
250
50
100
120
10
450
10
300
200
1000
t
ネットワークの最大フロー
• ネットワークの重みを、単
位時間にその辺へ流すこ
とのできる最大の水量と
みなす。
• このとき、頂点 s から t
へ流すことのできる最大
の水量を最大フローとい
う。
150
450
100
120
100
s
250
50
10
450
10
300
200
100
1000
t
ネットワークの最大フロー
• ネットワークの重みを、単
位時間にその辺へ流すこ
とのできる最大の水量と
みなす。
• このとき、頂点 s から t
へ流すことのできる最大
の水量を最大フローとい
う。
120
150
450
100
120
100
s
250
20
50
+10
10
250
450
10
300
200
100
1000
t
ネットワークの最大フロー
• ネットワークの重みを、単
位時間にその辺へ流すこ
とのできる最大の水量と
みなす。
• このとき、頂点 s から t
へ流すことのできる最大
の水量を最大フローとい
う。
120
150
450
100
120
100
370
s
250
20
50
10
10
200
100
+10
260
250
450
260
300
370
1000
t
370
最大フロー最小カット定理
s
450
100
50
120
250
10
100
450
120
100
10
200
120
150
450
370
s
250
20
50
10
10
300
260
250
450
260
300
最小
200
最小カットに含まれる辺には
100
370
1000
1000
最大フローでは容量一杯に
370
水が流れている。
t
t
370
最大フロー最小カット定理
• 最大フローと最小カットの値は一致する。
⇒ 容量一杯に水が流れている辺をうまく取ると、最小
カットになる。
370
s
250/250
100/100
10/10
370
t
10/10
容量一杯に水が流れている辺
最小 s-t カット問題(まとめ)
• 辺に重みを持つ連結なグラフ G が与えられ、2つの
頂点 s, t が指定されたとき、 s-t カットのうちで、重
みの総和が最小となるものを求めよ。
• 最小 s-t カット問題は、最大フローアルゴリズムを用
いて、多項式時間で解くことができる。
多分割カットと k-カット(目次)
• (寄り道) 最小 s-t カット問題
• 多分割カット問題
• 最小 k-カット問題
多分割カット問題
• 辺に重みを持つ連結なグラフ G が与えられ、k 個
の頂点 s1, s2, …, sk が指定されたとき、次の性質
をもつ辺集合のうちで、重みの総和が最小となるも
のを求めよ:
• その辺集合に属する辺をすべて取り除くと、グラフ
G は s1 を含む部分グラフ,s2 を含む部分グラ
フ,・・・,sk を含む部分グラフというように、k 個の部
分グラフに分割される。
• このような辺集合を多分割カット という。
多分割カット問題
重み付きグラフ G
重み付きグラフ G
s
S1
S2
S4
t
S3
多分割カット問題
• 多分割カット問題を解く多項式時間アルゴリズムは
存在するか?
• 答え: たぶん存在しない
多分割カット問題は「NP困難」
P=NPでない限り、この問題を解く多項式時間
アルゴリズムは存在しない。
多分割カット問題
とにかく考えてみる
S2
5
10
2
2
1
2
10
1
10
1
5
2
2
S1
10
2
5
1
1
3
3
5
S4
3
1
1
S3
多分割カット問題
• ムリ
• 第Ⅰ部の主旨:
– NP困難な問題に対して、ナイーブなアルゴリズ
ムの近似率を解析する。
⇒ 最小の多分割カットを求めることは諦めて、無駄
はあるかもしれないが、とりあえず多分割カットとな
る辺集合を求める。
多分割カット問題
(ナイーブなアルゴリズムを考える)
•
「最小 s-t カットを求めるアルゴリズム」を使った3
つの単純なアルゴリズム:
A) どんどん分割型アルゴリズム
B) 孤立カット-削除型アルゴリズム
C) 孤立カット-全体型アルゴリズム
多分割カット問題
(A)どんどん分割型アルゴリズム
重み付きグラフ G
S2
S1
S3
S5
S4
多分割カット問題
(B)孤立カット-削除型アルゴリズム
重み付きグラフ G
S2
S1
孤立カット
S3
S5
S4
多分割カット問題
(C)孤立カット-全体型アルゴリズム
S2 の孤立カット
重み付きグラフ G
S2
20
S3 の孤立カット
30
S1
S3
S1 の孤立カット
18
S5 の
孤立カット
15
S5
S4
S4 の孤立カット
9
多分割カット問題
(ナイーブなアルゴリズムを考える)
•
「最小 s-t カットを求めるアルゴリズム」を使った3
つの単純なアルゴリズム:
A) どんどん分割型アルゴリズム
B) 孤立カット-削除型アルゴリズム
C) 孤立カット-全体型アルゴリズム
p.40 アルゴリズム 4.3
①
②
③
④
最小重み孤立カットを求めるアルゴリズム
アルゴリズム(C)の近似率は2-2/k
タイトな例
アルゴリズム(A)と(B)に対するコメント
多分割カット問題
(孤立カットを求める)
• 「最小重み孤立カット」を求めるアルゴリズムを考え
る:
• 孤立させたいターミナル(指定された頂点)を s とし
たとき、s 以外のターミナルを同一視したグラフを作
り(その頂点を t とする)、最小 s-t カットを求める。
• このときの最小 s-t カットが、 s に対する「最小重み
孤立カット」となる。
孤立カットを求める
S2
5
10
2
2
1
1
3
2
10
5
1
1
10
1
5
2
2
S1
10
2
5
1
1
5
S1 の最小孤立カットS4
3
3
3
1
1
S3
孤立カットを求める
• 本当に最小孤立カットになっているか?
• S1 以外のターミナルを同一視したグラフ G’ の s-t
カットは、もとのグラフ G の孤立カットである。
G
s
G’
s
t
孤立カットを求める
• 本当に最小孤立カットになっているか?
• S1 以外のターミナルを同一視したグラフ G’ の s-t
カットは、もとのグラフ G の孤立カットである。
• G の孤立カットは、すべて G’ における s-t カットで
ある。
G
s
G’
s
t
孤立カットを求める
• 本当に最小孤立カットになっているか?
• S1 以外のターミナルを同一視したグラフ G’ の s-t
カットは、もとのグラフ G の孤立カットである。
• G の孤立カットは、すべて G’ における s-t カットで
ある。
• G の孤立カットの集合 = G’ の s-t カットの集合
• 最小 s-t カット = 最小孤立カット
多分割カット問題
• 最小 s-t カットを求めるアルゴリズムにより、最小孤
立カットを求めることができた。
• 次は、アルゴリズム 4.3 の近似率が 2-2/k となるこ
とを示す。
アルゴリズム 4.3
1. 各 i=1,…,k に対して、si に対する最小重み孤立カット Ci
を求める;
2. これらのカットで重み最大のものを1つ除いて、残りのカッ
トの和集合をとり、それを C として出力する.
多分割カット問題
(アルゴリズム 4.3)
C = C1 ∪C2 ∪C4 ∪C5
S2
最大
S1
C2
C1
C3
C5
S5
C4
S4
S3
多分割カット問題
(アルゴリズム4.3の近似率)
最小多分割カットを A とする。
S2
最適解 A
cost(C)≦(2-2/k)cost(A)?
S1
S3
S5
S4
多分割カット問題
(アルゴリズム4.3の近似率)
最小多分割カットを A とする。
S2 の孤立カット A2
S2
最適解 A
S3 の孤立カット A3
S1
S3
S1 の孤立カット A1
S5
S5 の孤立カット A5
S4
S4 の孤立カット A4
多分割カット問題
(アルゴリズム4.3の近似率)
• Ai の直和集合には、 A の要素が2つづつ含まれる。
• つまり、A = {e1, e2, … , em } とおくと、
∑1≦i≦k Ai = {e1, e1, e2, e2, … , em , em }
となる。
• したがって、 Ai のコストの総和は、 A のコストの2
倍となる。すなわち、
∑1≦i≦k cost(Ai ) = 2・cost(A)
が成り立つ。
多分割カット問題
(アルゴリズム4.3の近似率)
• アルゴリズム4.3 の出力は
C = ∪1≦i≦k Ci ー Cmax
ただし、 Ci はターミナル Si の最小孤立カット、 Cmax
は Ci の中でコストが一番高いものである。
• すべての i に対して cost(Ci) ≦ cost(Ai) が成り立
つので、
cost(C) ≦ ∑1≦i≦k cost(Ci )
≦ ∑1≦i≦k cost(Ai )
が成り立つ。
= 2・cost(A)
多分割カット問題
(アルゴリズム4.3の近似率)
• 最大重みの孤立カット Cmax のコスト は、Ci のコスト
の総和の平均以上である。すなわち、
cost(Cmax) ≧ 1/k ・∑1≦i≦k cost(Ci )
である。したがって、
cost(C) ≦ ∑1≦i≦k cost(Ci ) ー cost(Cmax)
≦ (1-1/k) ・∑1≦i≦k cost(Ci )
≦ (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
多分割カット問題
(アルゴリズム4.3の近似率)
cost(C) ≦ (2-2/k) ・cost(A)
• アルゴリズム4.3によって得られた解のコストは、最
適解のコストの (2-2/k) 倍以下となることがわかっ
た。
• アルゴリズム4.3の近似率は、これ以上改善されな
いのか?
• 答え: されない ∵ タイトな例が存在
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
S2
S1
2-ε
2-ε
1
1
Sk
1
2-ε
2-ε
1
1
2-ε
Sk-1
2-ε
Sk-2
S3
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
k=4 の場合
S1
C1
S2
2-ε
2-ε
1
1
2-ε
1
1
2-ε
2-ε
2-ε
S4
S3
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
k=4 の場合
S1
C1
S2
C2
2-ε
2-ε
1
C = C1 ∪C2 ∪C3
1
1
2-ε
C4
S4
1
cost(C) = 3・(2-ε)
= (k-1)・(2-ε)
2-ε
C3
S3
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
k=4 の場合
S1
S2
2-ε
1
2-ε
cost(A) = 4 = k
1 最適解 A 1
2-ε
S4
1
2-ε
S3
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
• 一般の k に対して、
cost(C) = (k-1)・(2-ε) 及び cost(A) = k
が成り立つことがわかった。したがって、
cost(C) / cost(A) = (1–1/k)・(2–ε)
= (2–2/k) –ε(1–1/k)
となる。これは、アルゴリズム 4.3 が (2–2/k) より小さい近似
率を達成できないことを示している。
• (どんなに小さい正数δに対しても、近似率 (2–2/k) –δを達
成できたとすると、ε<δ/ (1–1/k) が成り立つようにεを取れ
ば、上式により、cost(C) / cost(A) > (2–2/k) –δが成り立
つようなインスタンスを作ることができ、矛盾が生じる。)
多分割カット問題
(アルゴリズム4.3に対するタイトな例)
•
•
アルゴリズム4.3 の近似保証は (2–2/k) であるこ
とがわかった。
最後に、ナイーブなアルゴリズム(A)と(B)の近似
率について考察する。
A) どんどん分割型アルゴリズム
B) 孤立カット-削除型アルゴリズム
•
アルゴリズム4.3 に対するタイトな例に対して、こ
れらのアルゴリズムを適用してみる。
多分割カット問題
(A)どんどん分割型アルゴリズム
k=4 の場合
S1
S2
2-ε
1
2-ε
アルゴリズム4.3 と
1
1
同じ解が得られた
2-ε
S4
1
2-ε
S3
多分割カット問題
(B)孤立カット-削除型アルゴリズム
k=4 の場合
S1
S2
2-ε
2-ε
1
1
2-ε
1
1
2-ε
2-ε
2-ε
S4
S3
多分割カット問題
(B)孤立カット-削除型アルゴリズム
k=4 の場合
S2
2-ε
1
1
2-ε
1
1
2-ε
2-ε
S4
S3
多分割カット問題
(B)孤立カット-削除型アルゴリズム
k=4 の場合
S1
S2
2-ε
1
2-ε
アルゴリズム4.3 と
1
1
同じ解が得られた
2-ε
S4
1
2-ε
S3
多分割カット問題
(ナイーブなアルゴリズム(A)と(B)について)
• アルゴリズム 4.3 に対するタイトな例に対して、ナ
イーブなアルゴリズム(A)及び(B)を適用すると、
どちらもアルゴリズム 4.3 と同じ解を出力した。
• アルゴリズム(A)と(B)の近似率が解析できたとし
ても、 (2–2/k) より良い近似率を得ることはできな
い。
注:(A)に関しては、グリーディにカットしていくと、近似率
(2–2/k) が達成されると述べられている(演習問題 4.2)。
多分割カット問題(まとめ)
• 多分割カット問題に対して、最小 s-t カットアルゴリ
ズムを用いたナイーブなアルゴリズムが、(2–2/k)
の近似率を保証していることがわかった。
• 多分割カット問題に対する、より良い近似保証を持
つアルゴリズムは存在するか?
• 答え: 存在する
⇒ 第Ⅱ部 第19章にて解説
多分割カットと k-カット(目次)
• (寄り道) 最小 s-t カット問題
• 多分割カット問題
• 最小 k-カット問題
最小 k-カット問題
• 自然数 k と、辺に重みを持つ連結なグラフ G が与
えられたとき、次の性質をもつ辺集合のうちで、重み
の総和が最小となるものを求めよ:
• その辺集合に属する辺をすべて取り除くと、グラフ
G は、k 個の連結成分に分割される。
• このような辺集合を k-カット という。
最小 k-カット問題
多分割カット問題
S1
k=4
S2
S4
S3
最小 k-カット問題
最小 k-カット問題
• 最小 k-カット問題を解く多項式時間アルゴリズムは
存在するか?
• 答え: たぶん存在しない
最小 k-カット問題は「NP困難」
P=NPでない限り、この問題を解く多項式時間
アルゴリズムは存在しない。
最小 k-カット問題
とにかく考えてみる
5
10
2
2
k=4
1
10
2
2
10
1
10
1
5
2
2
5
1
1
5
3
3
3
1
1
最小 k-カット問題
• やっぱりムリ
• 第Ⅰ部の主旨:
– NP困難な問題に対して、ナイーブなアルゴリズ
ムの近似率を解析する。
⇒ 最小の k-カットを求めることは諦めて、無駄はあ
るかもしれないが、とりあえず k-カットとなる辺集合
を求める。
最小 k-カット問題
• ナイーブなアルゴリズム?
• 多項式時間でできること:
– 最小 s-t カットを求める
– 最小孤立カットを求める
– 多分割カット問題の (2-2/k) 近似解を求める
• これらのアルゴリズムは、ターミナルの概念を含ん
でいる。
⇒ もっと道具が必要
最小 k-カット問題
• これからの道筋
– Gomory-Hu 木
– Gomory-Hu 木を用いた k-カットアルゴリズム
– アルゴリズムの近似率解析
– タイトな例
Gomory-Hu 木
•
G=(V,E) を重み付き連結グラフとする。このとき、
G の頂点上をわたる重み付きの木 T=(V,F) が G
に対する Gomory-Hu 木であるとは、次の2つの
条件を満たすときである:
1. 任意の u,v∈V に対して、G の最小 u-v カット
の重みと T の最小 u-v カットの重みが等しい。
2. T における辺 e∈F の重みは、e によって分割さ
れる頂点集合を、G 上で分割する際のコスト
(カットの重み)と等しい。
Gomory-Hu 木
G の頂点上をわたる木
T=(V,F)
重みつきグラフ G=(V,E)
b
c
4
5
10
2
a
2
3
d
4
2
8
7
f
3
e
Gomory-Hu 木
G の頂点上をわたる木
T=(V,F)
b
c
d
a
f
e
Gomory-Hu 木
G の頂点上をわたる木
T=(V,F)
重みつきグラフ G=(V,E)
b
c
4
5
10
2
a
2
3
d
4
2
8
7
f
3
もとのグラフ G に
無い辺があっても良い
e
Gomory-Hu 木
18 (10+8) b
1. 任意の u,v∈V に対して、G の最小
u-v カットの重みと T の最小 u-v
カットの重みが等しい。
4
5
10
a
c
2
3
8
b
7
c
f
18
a
d
17
15
14
13
f
e
d
2 4
2
3
e
Gomory-Hu 木
1. 任意の u,v∈V に対して、G の最小
u-v カットの重みと T の最小 u-v
カットの重みが等しい。
a
b
c
13 (4+2+2+3+2)
b
c
4
5
10
2 4
2
d
2
3
8
7
3
f
e
18
a
d
17
15
14
13
f
e
すべての頂点の組
(u,v) に対して成り
立つ
Gomory-Hu 木
2. T における辺 e∈F の重みは、e に
よって分割される頂点集合を、G 上
で分割する際のコスト(カットの重み)
と等しい。
b
a
c
13 (4+2+2+3+2)
b
c
4
5
10
2
2 4
d
2
3
8
7
3
f
e
18
a
d
17
15
14
13
f
e
辺 (f,e) に付随するカット
Gomory-Hu 木
2. T における辺 e∈F の重みは、e に
よって分割される頂点集合を、G 上
で分割する際のコスト(カットの重み)
と等しい。
b
a
c
17 (4+2+3+8)
b
c
4
5
10
d
2
2 4
3
2
8
7
3
f
e
18
a
d
17
15
14
13
f
e
辺 (b,f) に付随するカット
すべての辺 e∈F に
おいて成り立つ
Gomory-Hu 木
• こんな都合の良い木が本当にあるのか?
– 任意の重み付き連結グラフ G に対して、 Gomory-Hu 木
TG は必ず存在するのか?
– 答え: 存在する(?)
• Gomory-Hu 木を効率的に求めるアルゴリズムはあ
るか?
– 任意の重み付き連結グラフ G に対して、 Gomory-Hu 木
TG を構成する多項式時間アルゴリズムは存在するか?
– 答え: 存在する(演習問題 4.6)
Gomory-Hu 木を用いた
k-カットアルゴリズム
• 最小 k-カット問題:
– グラフ G と自然数 k が与えられたとき、 G の k-カットの
うちで、コスト最小のものを求めよ。
アルゴリズム 4.7
1. G に対する Gomory-Hu 木 TG を求める。
2. TG の n-1 個の辺のうち、重みの小さい方から k-1 個の
辺を選び出す。
3. 選び出された k-1 個の辺それぞれについて、付随する
G のカットを求める。
4. 求まった k-1 個のカットの和集合 C を出力する。
n : G の頂点数
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
5
10
a
c
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
1. G に対する Gomory-Hu
木 TG を求める。
b
c
18
a
17
d
15
14
13
f
e
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
5
10
a
c
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
2. TG の n-1 個の辺のうち、
重みの小さい方から k-1
個の辺を選び出す。
b
c
18
a
17
d
15
14
13
f
e
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
5
10
a
c
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
3. 選び出された k-1 個の辺
それぞれについて、付随
するG のカットを求める。
b
c
18
a
17
d
15
14
13
f
e
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
5
10
a
c
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
3. 選び出された k-1 個の辺
それぞれについて、付随
するG のカットを求める。
b
c
18
a
17
d
15
14
13
f
e
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
5
10
a
ちょうど3つの連結
成分に分割された
c
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
4. 求まった k-1 個のカットの
和集合 C を出力する。
b
c
18
a
17
d
15
14
13
f
e
注意!
• 一般に、連結グラフ G における k-1 個のカットの和
集合は、G をちょうど k 個の連結成分に分割する
か?
• 答え: しない
連結グラフ G
連結グラフ G
②
①
②
③
①
③
④
さらに注意!
• 一般に、連結グラフ G における k-1 個のカットの和
集合は、G を k 個以上の連結成分に分割するか?
連結グラフ G
連結グラフ G
さらに注意!
• 一般に、連結グラフ G における k-1 個のカットの和
集合は、G を k 個以上の連結成分に分割するか?
• 答え: しない
4個のカット
4個の連結成分
アルゴリズム 4.7 の問題点
• アルゴリズム 4.7:
– G の k-1 個のカットの和集合 C を出力。
– しかし、C が G を k 個の連結成分に分割する保証は無
い。
• 次のことを証明する必要があった(補題4.6):
– 重み付き連結グラフ G に対する Gomory-Hu 木を TG と
する。このとき、TG の ℓ 個の辺に付随する G のカットの
和集合 S は G を ℓ +1 個以上の連結成分に分割する。
アルゴリズム 4.7 の問題点
(補題 4.6 の証明)
• 補題 4.6 を証明するためには、次のことを考えれば
よい:
• 任意の木は、ℓ 個の辺を取り除くと、 ℓ +1 個の連結
成分に分割される。
アルゴリズム 4.7 の問題点
(補題 4.6 の証明)
• Gomory-Hu 木 TG は、ℓ 個の辺を取り除くと、 ℓ +1 個の連
結成分に分割される。
• 分割された TG の連結成分の頂点集合をそれぞれ
V1,V2,…,Vℓ +1 とする。
4.7 により得られる
• グラフ Gアルゴリズム
においても、対応する頂点集合は、辺に付随する
カットによって分割される。
k-1 個のカットの和集合は、必ず
b グラフ
4
5
10
a
b
c k 個以上に分割する
Gを
2
3
8
18
d a
2 4
2
17
7
f
3
e
重み付き連結グラフ G
c
d
15
14
13
f
e
G に対する Gomory-Hu 木 TG
アルゴリズム 4.7 の問題点
(補題 4.6 の証明)
• グラフ G の頂点上をわたる木を考えると、これらの
カットのうち、必ず一つは、二つ以上の辺をまたぐも
のとなっている。
この4つが選ばれ
たときに、和集合
は、G を4つの連
結成分にしか分割
しなかった。
このカットは、アル
ゴリズムでは選ば
れない
アルゴリズム 4.7 の問題点
(補題 4.6 の証明)
• 以上により、アルゴリズム 4.7 で得られる k-1 個の
カットの和集合 C は、グラフ G を k 個以上の連結
成分に分割することが分かった。
• ちょうど k 個の連結成分にしたいなら、適当な辺を
戻してやればよい。
• 次は、アルゴリズム 4.7 が近似率 (2-2/k) を達成す
ることを証明する。
• k+1 個以上の連結成分に分割されていたとしても、
C のコストは最適解コストの (2-2/k) 倍以下に抑え
られる。
最小 k-カット問題
(アルゴリズム4.7の近似率)
最小 k-カットを A とする。
最適解 A
cost(C)≦(2-2/k)cost(A)?
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
最小 k-カットを A とする。
最適解 A
A2
A3
V2
V1
A1
V3
V5
V4
A5
A4
最小 k-カット問題
(アルゴリズム4.7の近似率)
• Ai の直和集合には、 A の要素が2つづつ含まれる。
• つまり、A = {e1, e2, … , em } とおくと、
∑1≦i≦k Ai = {e1, e1, e2, e2, … , em , em }
となる。
• したがって、 Ai のコストの総和は、 A のコストの2
倍となる。すなわち、
∑1≦i≦k cost(Ai ) = 2・cost(A)
が成り立つ。
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• cost(C) ≦ ∑1≦i≦k-1 cost(fi )
f1 ~ fk-1 : TG の辺コストの小さいほうから k-1 個
– C は、 TG の辺コストの小さいほうから k-1 個選び、それぞ
れに付随する G のカットの和集合をとったもの
– Gomory-Hu 木の性質2より、 TG の辺コストと、それに付
随する G のカットのコストは同じ
– したがって成り立つ
Gomory-Hu 木を用いた
k-カットアルゴリズム
重み付き連結グラフ G
k=3
b
4
cost(C)=25≦13+14=27
14
c
Gomory-Hu 木の性質2から、そ
れぞれの辺に付随するカットのコ
ストは一致する。
5
10
a
13
2
3
d
2 4
2
8
7
f
3
G に対する Gomory-Hu 木 TG
e
b
c
18
この辺が両方のカット
に含まれている
a
17
d
15
14
13
f
e
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• ∑1≦i≦k-1 cost(fi ) ≦ ∑1≦i≦k-1 cost(bi )
f1~fk-1 : TG の辺コストの小さいほうから k-1 個
b1~bk-1 : ある性質を満たす T の辺 (k-1 個)
• bi が TG の辺である限り、 bi のコストの総和は fi の
コストの総和を超えてしまう。
b
b
c
18
a
c
18
17
d a
15
14
13
f
17
e
d
15
14
13
f
e
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• ∑1≦i≦k-1 cost(bi )
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
b1~bk-1 : ある性質を満たす TG の辺 (k-1 個)
• ある性質とは、任意の i (1≦i≦k-1) に対して
cost(bi ) ≦ cost(Ai )
が成り立つことである。ただし、 Ak = Amax とする。
• このような bi が存在するかどうかは、後で議論する。
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
?≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• Amax のコスト は、Ai のコストの総和の平均以上で
ある。すなわち、
cost(Amax) ≧ 1/k ・∑1≦i≦k cost(Ai )
が成り立つ。
平均
最小 k-カット問題
(アルゴリズム4.7の近似率)
• Amax のコスト は、Ai のコストの総和の平均以上で
ある。すなわち、
cost(Amax) ≧ 1/k ・∑1≦i≦k cost(Ai )
が成り立つ。したがって、
∑1≦i≦k cost(Ai ) ー cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
?≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
• ∑1≦i≦k-1 cost(bi )
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
b1~bk-1 : ある性質を満たす TG の辺 (k-1 個)
• ある性質とは、任意の i (1≦i≦k-1) に対して
cost(bi ) ≦ cost(Ai )
が成り立つことである。ただし、 Ak = Amax とする。
• このような bi が存在するかどうかは、後で議論する。
最小 k-カット問題
(アルゴリズム4.7の近似率)
• これから示すこと:
• Gomory-Hu 木 TG には、 任意の i (1≦i≦k-1) に対
して、
cost(bi ) ≦ cost(Ai )
が成り立つような、 k-1 個の辺 b1, b2, …, bk-1 が存
在する。
最適解 A
A2
ただし、 Ai は最適解 A から
A3
V2
得られる G のカットであり、
V1
V3
Ak は最大コストとする。
V
V
A1
5
4
A5
A4
最小 k-カット問題
(アルゴリズム4.7の近似率)
最適解によってカットされる Gomory-Hu 木の辺に
注目する
最適解 A
V2
V1
V3
V5
V4
この辺集合
を B とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
各 Vi を一つの頂点として見る
最適解 A
V2
V1
V3
V5
V4
この辺集合
を B とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
各 Vi を一つの頂点として見る
最適解 A
V2
V1
V3
V5
V4
この辺集合
を B とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
このグラフが木となるように、B の中から辺を選ぶ
最適解 A
V2
V1
V3
V5
V4
この辺集合
を B’ とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
Ai のコストが最大となるような Vi を根として、
木を有向化する
最適解 A
A2
A3
V2
V1
A1
V3
V5
この辺集合
を B’ とおく
V4
最大
A5
A4
最小 k-カット問題
(アルゴリズム4.7の近似率)
Ai のコストが最大となるような Vi を根として、
木を有向化する
最適解 A
V2
V1
V3
V5
最大
V4
この辺集合
を B’ とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
各 Vi から出る辺を bi と名付ける
最適解 A
V2
b2
V1
b3
V3
b4
b1
V5
最大
V4
この辺集合
を B’ とおく
最小 k-カット問題
(アルゴリズム4.7の近似率)
各 Vi から出る辺を bi と名付ける
最適解 A
V2
V1
V3
V5
最大
V4
最小 k-カット問題
(アルゴリズム4.7の近似率)
これらの bi は、Gomory-Hu 木の辺であった
最適解 A
V1
b2
V2
V5
最大
最適解 A
b3
V3
b4
b1
Gomory-Hu 木
V4
b3
b2
b1
b4
最小 k-カット問題
(アルゴリズム4.7の近似率)
これらの bi は、Gomory-Hu 木の辺であった
Gomory-Hu 木
最適解 A
b3
b2
b1
b4
最小 k-カット問題
(アルゴリズム4.7の近似率)
Gomory-Hu 木の性質1に注目:
任意の u,v∈V に対して、G の最小 u-v カットの重みと
TG の最小 u-v カットの重みが等しい。
最適解 A
b1 の重みは、G の
最小 u-v カットの
コストに等しい
u
b3
b2
b1
A1
A1 は、G における u-v カット
v
b4
最小 k-カット問題
(アルゴリズム4.7の近似率)
• cost(b1) = G における最小 u-v カットのコスト
• A1 は G における u-v カットの一つである
• 最小 u-v カットのコスト ≦ u-v カットのコスト
⇒cost(b1) ≦ cost(A1)
• 同様のことが、他の bi に対しても成り立つ。
• したがって、任意の i (1≦i≦k-1) に対して、
cost(bi) ≦ cost(Ai)
が成り立つ。
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 以下のことが示された:
• Gomory-Hu 木 TG には、 任意の i (1≦i≦k-1) に対
して、
cost(bi ) ≦ cost(Ai )
が成り立つような、 k-1 個の辺 b1, b2, …, bk-1 が存
在する。
最適解 A
A2
ただし、 Ai は最適解 A から
A3
V2
得られる G のカットであり、
V1
V3
Ak は最大コストとする。
V
V
A1
5
4
A5
A4
最小 k-カット問題
(アルゴリズム4.7の近似率)
• ∑1≦i≦k-1 cost(bi )
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
b1~bk-1 : ある性質を満たす TG の辺 (k-1 個)
• ある性質とは、任意の i (1≦i≦k-1) に対して
cost(bi ) ≦ cost(Ai )
が成り立つことである。ただし、 Ak = Amax とする。
• このような bi が存在することが示された。
最小 k-カット問題
(アルゴリズム4.7の近似率)
• 証明のアイデア:
cost(C)
≦ ∑1≦i≦k-1 cost(fi )
TG の辺コストの小さいほうから k-1 個
≦ ∑1≦i≦k-1 cost(bi )
ある性質を満たす TG の辺 (k-1 個)
≦ ∑1≦i≦k cost(Ai ) - cost(Amax)
≦ ∑1≦i≦k cost(Ai ) - 1/k・∑1≦i≦k cost(Ai )
= (1-1/k) ・ ∑1≦i≦k cost(Ai )
= (1-1/k) ・ 2・cost(A) = (2-2/k) ・cost(A)
最小 k-カット問題
(アルゴリズム4.7の近似率)
cost(C) ≦ (2-2/k) ・cost(A)
• アルゴリズム4.7によって得られた解のコストは、最
適解のコストの (2-2/k) 倍以下となることがわかっ
た。
• アルゴリズム4.7の近似率は、これ以上改善されな
いのか?
• 答え: されない ∵ タイトな例が存在
最小 k-カット問題
(アルゴリズム4.7に対するタイトな例)
k=K に対して、
頂点数が 2K と
なるようにとる
2-ε
2-ε
1
1
1
2-ε
2-ε
1
1
2-ε
2-ε
最小 k-カット問題
(アルゴリズム4.7に対するタイトな例)
k=4 の場合
2-ε
2-ε
2-ε
1
1
2-ε
1
1
2
2-ε
重み付き連結グラフ G
2-ε
2
2-ε
2
2-ε
G に対する Gomory-Hu 木 TG
cost(C) = 3・(2-ε) = (k-1)・(2-ε)
最小 k-カット問題
(アルゴリズム4.7に対するタイトな例)
k=4 の場合
2-ε
1
2-ε
cost(A) = 4 = k
1 最適解 A 1
2-ε
1
2-ε
最小 k-カット問題
(アルゴリズム4.7に対するタイトな例)
• 一般の k に対して、
cost(C) = (k-1)・(2-ε) 及び cost(A) = k
が成り立つことがわかった。したがって、
cost(C) / cost(A) = (1–1/k)・(2–ε)
= (2–2/k) –ε(1–1/k)
となる。これは、アルゴリズム 4.7 が (2–2/k) より小さい近似
率を達成できないことを示している。
• (どんなに小さい正数δに対しても、近似率 (2–2/k) –δを達
成できたとすると、ε<δ/ (1–1/k) が成り立つようにεを取れ
ば、上式により、cost(C) / cost(A) > (2–2/k) –δが成り立
つようなインスタンスを作ることができ、矛盾が生じる。)
最小 k-カット問題(まとめ)
• 最小 k-カット問題に対して、Gomory-Hu 木を用い
たアルゴリズムが、(2–2/k) の近似率を保証してい
ることがわかった。
• 最小 k-カット問題に対する、より良い近似保証を持
つアルゴリズムは存在するか?
• 答え: ????