Qianping Gu (Simon Fraser大)

Slides:



Advertisements
Similar presentations
ベイズの定理と ベイズ統計学 東京工業大学大学院 社会理工学研究科 前川眞一. 2 Coffe or Tea 珈琲と紅茶のどちらが好きかと聞いた場合、 Star Trek のファンの 60% が紅茶を好む。 Star Wars のファンの 95% が珈琲を好む。 ある人が紅茶を好むと分かったとき、その人が.
Advertisements

だい六か – クリスマスとお正月 ぶんぽう. て form review ► Group 1 Verbs ► Have two or more ひらがな in the verb stem AND ► The final sound of the verb stem is from the い row.
て -form - Making て -form from ます -form -. With て -form, You can say... ~てもいいですか? (= May I do…) ~てください。 (= Please do…) ~ています。 (= am/is/are doing…) Connecting.
第 5 章 2 次元モデル Chapter 5 2-dimensional model. Contents 1.2 次元モデル 2-dimensional model 2. 弱形式 Weak form 3.FEM 近似 FEM approximation 4. まとめ Summary.
Essay writing rules for Japanese!!. * First ・ There are two directions you can write. ・よこがき / 横書き (same as we write English) ・たてがき / 縦書き (from right to.
VE 01 え form What is え form? え? You can do that many things with え form?
ロジスティクス工学 第6章 動的ロットサイズ決定モデル 東京商船大学 久保 幹雄
英語勉強会.
THE CONTINUOUS IMPROVEMENT MODEL called ADEC
Chapter 11 Queues 行列.
日本語... ジェパディー! This is a template for you to use in your classroom.
AP/5 2013年2月7日.
    有限幾何学        第8回.
Chris Burgess (1号館1308研究室、内線164)
Approximation of k-Set Cover by Semi-Local Optimization
What did you do, mate? Plain-Past
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
Paper from PVLDB vol.7 (To appear in VLDB 2014)
Noun の 間(に) + Adjective Verb てform + いる間(に) during/while.
項書換え系(3) 合流性 Term Rewriting Systems(3) Confluence 知能ソフトウェア特論
点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日
Tohoku University Kyo Tsukada
V 03 I do NOT eat sushi. I do NOT do sumo.
Licensing information
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
Chapter 4 Quiz #2 Verbs Particles を、に、で
定期考査2 英語.
The Sacred Deer of 奈良(なら)
Did he/she just say that? Get your head out of the gutter! Oh wait….
CRLA Project Assisting the Project of
VTA 02 What do you do on a weekend? しゅうまつ、何をしますか。
Nihongo Japanese 日本ご ‘Numbers ’ & ‘Hiragana Revision’
Chapter 1 Hamburger History
ストップウォッチの カード ストップウォッチの カード
Topics on Japan これらは、過去のインターンが作成したパワポの写真です。毎回、同じような題材が多いため、皆さんの出身地等、ここにない題材も取り上げるようにしてください。
ロジスティクス工学 第7章 配送計画モデル 東京商船大学 久保 幹雄
シャノンのスイッチングゲームにおけるペアリング戦略について
How long does it take かかります.
The Syntax of Participants シンタックスの中の話者と聞き手
点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日
Causative Verbs Extensively borrowed from Rubin, J “Gone Fishin’”, Power Japanese (1992: Kodansha:Tokyo) Created by K McMahon.
1 T 行きがけ順: A B D F I J C G H 通りがけ順: D B I F J A G C H
-Get test signed and make corrections
Where is Wumpus Propositional logic (cont…) Reasoning where is wumpus
豊田正史(Masashi Toyoda) 福地健太郎(Kentarou Fukuchi)
Question Words….
25. Randomized Algorithms
クイズやゲーム形式で紹介した実例です。いずれも過去のインターン作です。
東北大学大学院情報科学研究科 教授 西関 隆夫
2019年4月8日星期一 I. EPL 84, (2008) 2019年4月8日星期一.
Satoshi Kawashima, LLD 川島 聡 University of Tokyo
2019/4/22 Warm-up ※Warm-up 1~3には、小学校外国語活動「アルファベットを探そう」(H26年度、神埼小学校におけるSTの授業実践)で、5年生が撮影した写真を使用しています(授業者より使用許諾済)。
14. The Basic Method M1 太田圭亮 14.3 Spaces of polynomials
Genetic Statistics Lectures (4) Evaluation of a region with SNPs
北大MMCセミナー 第62回 附属社会創造数学センター主催 Date: 2016年11月4日(金) 16:30~18:00
知能ソフトウェア特論 Intelligent Software
知能ソフトウェア特論 Intelligent Software
ー生命倫理の授業を通して生徒の意識に何が生じたかー
Created by L. Whittingham
東北大 情報科学 田中和之,吉池紀子 山口大 工 庄野逸 理化学研究所 岡田真人
Max Cut and the Smallest Eigenvalue 論文紹介
MO装置開発 Core part of RTR-MOI Photograph of core part.
Cluster EG Face To Face meeting
~て しまう.
Grammar Point 2: Describing the locations of objects
BW: 英語で書いて下さい 1)小さくする 2)うるさく話す 3)大きく書く 4)上手になる (なる=become)
Apply sound transmission to soundproofing
点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日
アノテーションガイドラインの管理を行う アノテーションシステムの提案
Improving Strategic Play in Shogi by Using Move Sequence Trees
Presentation transcript:

Qianping Gu (Simon Fraser大) 平面グラフ分枝幅と分枝分割 明治大学理工学部情報科学科 玉木久夫 共同研究者: Qianping Gu (Simon Fraser大) 吉武由実(明治大学理工学研究科)

内容 Part 1 グラフの分枝幅と分枝分割:定義と背景 平面グラフの分枝分割アルゴリズム   O(n4) 時間アルゴリズム(Seymour & Thomas 94)    O(n3) 時間への改良(Gu & Tamaki 05) Part 2 平面グラフの分枝幅   ねずみ捕りゲームによる特徴づけとO(n2) 時間アルゴリズム (Seymour & Thomas 94) 特徴づけの理解: 実際的な改良へ向けて

Part 1

Branch-decomposition(分枝分割) A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f a c e g e a c g b d f b d G

Branch-decomposition A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f a c g e a c f e g b d b d G

Branch-decomposition A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f a c g f e a c b d e g b d G

Branch-decomposition A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f c a g f e a c b d e g b d G

Branch-decomposition A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f c a g f e a c b d b d e g G

Branch-decomposition A branch-decomposition of graph G : Conceptual definition: a recursive binary decomposition of E(G) f c a g f e a c b d g G b d e

Branch-decomposition A branch-decomposition of graph G : Formal definition: a ternary tree with leaf set E(G) f c a g f e a c b d g G b d e

Branch-decomposition A branch-decomposition of graph G : Formal definition: a ternary tree with leaf set E(G) … abstracts away the starting bipartition f c a g f e a c b d g G b d e

Branch-decomposition A branch-decomposition of graph G : Formal definition: a ternary tree with leaf set E(G) … abstracts away the starting bipartition … f c a g f e a c b d g G b d e

Branchwidth(分枝幅) G The width of branch-decomposition T of G : f a g e The maximum cardinality of the vertex cuts of G associated with the edges of T. f c a f a g e c b d G g b e d

Branchwidth G The width of branch-decomposition T of G : f a g e c d b The maximum cardinality of the vertex cuts of G associated with the tree edges of T. f c a f a g e c b d 3 G g b e d

Branchwidth G The width of branch-decomposition T of G : f a 2 g 3 e 2 The maximum cardinality of the vertex cuts of G associated with the tree edges of T. f width = 4 c a 2 g 3 f e a 2 c 2 4 b d 3 3 2 2 2 2 g G b d e

Branchwidth The branchwidth of G : The minimum width of all the branch-decompositions of G.

Background Branch-decompositions are introduced by Robertson and Seymour (1991) in relation to tree-decompositions. vertex cuts tree edges of a branch-decomposition. tree nodes of a tree-decomposition, bw(G) ≦ tw(G) + 1 ≦ (3/2) bw(G) Many NP-hard combinatorial problems on graphs can be solved in 2O(bw(G))n time, via DP based on the decomposition. .

Known results(Seymour-Thomas 94) General graphs:  NP-complete to decide whether bw(G) ≦ k for given G, k, if k is part of the input. Planar graphs:  The decision problem: O(n2) time Constructing the corresponding decomposition: O(n4) time If k is fixed, then the decision and the construction can both be done in linear time on general graphs (Bodlaender & Thilikos 97).  O(n3) : This work

Rest of Part 1 Carving decomposition Seymour-Thomas algorithm for planar graphs Key lemmas for improvement Algorithm and analysis: some ideas

Carving decomposition(刻み分割) of G A recursive binary decomposition of V(G) Formally a ternary tree with leaf set V(G). The width of carving decomposition T of G is the maximum cardinality of the edge cuts of G associated with tree edges of T. 5 3 5 4 1 1 5 4 2 3 2 G

Branch-decomposition vs carving-decomposition The problem of computing an optimal decomposition of planar graph G can be reduced to that of computing an optimal carving-decomposition of a related planar multi-graph M(G). (Seymour and Thomas 94).

Goal Tool: O(n2)-time Carving-width decision procedure (Seymour and Thomas 94) Given a planar multi-graph G with n vertices and O(n) edges, a minimum-width carving decomposition of G can be constructed in O(n3) time. Given a planar multi-graph G and a positive integer k, decides whether the carvingwidth of G exceeds k.

Bottom-up construction of a carving-decomposition Start from singleton sets of vertices. 1 2 3 6 4 5 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 3 6 4 5 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 6 4 4 5 5 7 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 4 6 4 5 5 7 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 4 6 4 5 5 7 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 4 6 4 5 5 7 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 4 6 4 5 5 7 7

Bottom-up construction of a carving-dec. Merge two vertex sets into one, at a time. 1 2 1 2 3 3 6 4 6 4 5 5 7 7

Bond carving Bond carving of G: a carving decomposition of G in which every cut bipartitions V(G) into two connected sets, i.e., every cut is a dual cycle Lemma (Seymour and Thomas 94)  In the bottom up process, we can only merge adjacent vertex sets For every planar multi-graph G, the optimal carvingwidth can be achieved by a bond carving.

How to guide the bottom-up construction We have a contracted multi-graph at each step. 1 2 3 6 4 5 7

How to guide the bottom-up construction We have a contracted multi-graph at each step. 1 2 3 6 5 7

How to guide the bottom-up construction We have a contracted multi-graph at each step. Use the width decision procedure to ensure that the carvingwidth does not exceed the original width at any step. 1 2 3 6 5 We say that two vertex sets X and Y are mergeable if merging them into one does not cause the carvingwidth to exceed the original optimal width 7

A carving-decomposition algorithm Decide the carvingwidth k of G. M  the set of all singleton vertex sets of G. While |M| > 1 do Find a mergeable pair X , Y of vertex sets in M and replace them by X U Y. At each iteration, the O(n2)-time decision procedure is called O(n) times for mergeability testing.  O(n4) time in total for n iterations

Our refinement Reduce the number of calls to the decision procedure througout the execution from O(n2) to O(n). The answers to all the other mergeability tests are deduced from previous test results in O(n) time each.

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, where k is the carving width of G X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. ≦ k W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. ? W Z X Y

Key lemma Let X, Y, W, Z be in the current set M of vertex sets, such that |dG(X U Y)| ≦ k, X and Y are not mergeable, No edge of G between W and Z. 4. X and W are mergeable and so are Y and Z. Let M’ be obtained from M by merging these two pairs Then, X UW and Y UZ are not mergeable in M’. W Z X Y

Proof of the key lemma Assume we have We assume that X UW and Y UZ are mergeable and show that X and Y would then be mergeable A Assume we have Z W X Y

Proof of the key lemma Assume we have then, we have or We assume that X UW and Y UZ are mergeable and show that X and Y would then be mergeable A A A Assume we have then, we have or W Z Z X Y Z W X Y W X Y

We only need to consider the red cuts below. Proof of the key lemma We only need to consider the red cuts below. (Blue cuts are ok by the assumption of the lemma) A A A W Z Z X Y Z W X Y W X Y

Proof of the key lemma (completed) cut1 + cut2 = cut3 + cut4 ≦ 2k So, either cut1 ≦ k or cut2 ≦ k Note there are no edges between W and Z by assumption 3 1 A W Z 2 X ∪Y 4

Finished? Only one expensive test between a pair, as long as the set of edges between them does not change? X Y

Finished? Only one expensive test between a pair, as long as the set of edges between them does not change? W1 Z1 X Y

Finished? Only one expensive test between a pair, as long as the set of edges between them does not change? W2 Z2 W1 Z1 X Y

Finished? Only one expensive test between a pair, as long as the set of edges between them does not change? W3 Z3 W2 Z2 W1 Z1 X Y

Finished? Problem: once the union of the pair has > k edges out, we cannot apply the lemma any more. ? W3 Z3 W2 Z2 > k W1 Z1 X Y

Need a better use of the lemma Forest view of the situation. ? Z3 W3 Z2 W2 Z1 W1 X Y

Need a better use of the lemma Forest view of the situation. ? Z3 W3 Z2 W2 Z1 W1 X Y

If we can rearrange the subtrees on the side … Z3 ? W2 Z2 W1 Z1 X Y

If we can rearrange the subtrees on the side … Then we can apply the lemma. W3 Z3 W2 Z2 W1 Z1 X Y

When are the rearrangements are possible? If the sizes of the red cuts do not exceed the optimal width k. W3 Z3 W2 Z2 W1 Z1

Barriers A descending chain in the constructed forest as below is called a barrier if |dG(Z1 U Z2 U … U Zj)| > k, Z1 Z2 Zj

Barrier-free chains The ‘side-subtrees’ along a descending chain can be rearranged into one subtree if no prefix of the chain is a barrier. Z1 Z1 Z2 Z2 Zj Zj

Our test of mergeability If |dG(X U Y)| > k then answer NO. ? X Y

Our test of mergeability Otherwise, identify maximal X’ ⊆ X and Y’ ⊆ Y in the forest s.t. EG(X, Y) = EG (X’, Y’) and the test for (X’, Y’) was executed with a negative answer. ? X’ Y’ X Y

Our test of mergeability If both of the chains from the root for X to the root for X’ and from the root for Y to the root for Y’ are barrier free, then answer NO. barrer-free barrer-free X’ Y’ X Y

Our test of mergeability Otherwise, call the O(n2)-time decision procedure. ? X’ Y’ X Y

Analysis Lemma: Using our test of mergeability, the O(n2)-time decision procedure is called O(n) times. Proof ideas  F = {(X, Y) | the decision procedure is called for (X, Y)} Equivalence relation       (X, Y) ~(X’, Y’) ⇔ EG(X, Y) = EG (X’, Y’) The number of equivalence classes in F are O(n). For each equivalence class C, |C| - 1 barriers are associated. We can choose O(n/k) representative barriers, so that To each element of F, one representative barrier is associated. O(k) elements of F are associated with each representative barrier.  |F| = O(n)

Total running time O(n) decision procedure calls, O(n2) time each … O(n3) O(n2) cheap tests, O(n) time each … O(n3) Maintenance of the contracted graphs: O(n) updates, O(n) time each … O(n2)

Open questions o(n3) time algorithm for planar branch-/carving-decomposition … difficult o(n2) time algorithm for planar branch-/carvingwidth … more difficult Polynomial time algorithm for the treewidth of planar graphs … super difficult.

Part 2

Gの辺 e が通行不能  e と ねずみ捕りのいる面または辺を通る、長さ k 未満の閉じた双対歩道が存在する。 ネズミ捕りゲーム 環境: 平面グラフ G, 正整数 k プレイヤ: ねずみ      ねずみ捕り ねずみは G の頂点に住み、辺を通って移動する。 ねずみ捕りはG の面に住み、双対辺を通って移動する。 お互いに、相手が見える。 ねずみ捕りは、騒音を発してねずみの移動を妨害する。 Gの辺 e が通行不能  e と ねずみ捕りのいる面または辺を通る、長さ k 未満の閉じた双対歩道が存在する。 e

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

ゲームの手順 (1) が面を選ぶ (2) が頂点を選ぶ 以下のラウンドを繰り返す (a) が現在の面に接する辺を選び、その上に移動 (1)    が面を選ぶ (2)    が頂点を選ぶ 以下のラウンドを繰り返す  (a)     が現在の面に接する辺を選び、その上に移動  (b)     が通行可能な辺を(いくつでも)通って行ける頂点を選び移動  (c)     が、辺から今までいたのと反対の面に移動 k = 4

勝敗決定 の勝利( の捕捉): が のいる頂点と接する面にいて、 のいる頂点の次数が k 未満である。 の勝利=永久に捕捉を免れる     の勝利(   の捕捉):       が   のいる頂点と接する面にいて、       のいる頂点の次数が k 未満である。 k = 4   の勝利=永久に捕捉を免れる

平面グラフの刻み幅(Carvingwidth)の特徴付け 定理(Seymour&Thomas 94) G: 平面グラフ   k: 正整数   Gの刻み幅が k 以上     ⇔ (G, k)上のねずみ捕りゲームがねずみ必勝

(→ 平面グラフの刻み幅決定アルゴリズム) 特徴づけ定理の証明 以下の内容 ねずみ捕りゲームの勝敗決定アルゴリズム   (→ 平面グラフの刻み幅決定アルゴリズム) 特徴づけ定理の証明 (1)やさしい方向   幅 k未満の刻み分割 => ねずみ捕りの必勝戦略 (2)難しい方向   幅 k未満の刻み分割の不在=> ねずみの必勝戦略   グラフマイナーシリーズの定理2つを使用 (2)の理解から得られる実際的な改良の方向

ねずみ捕りゲームの勝敗決定アルゴリズム 平面グラフ G とパラメータ k :固定 e : G の辺 2 6 k = 4 平面グラフ G とパラメータ k :固定 e : G の辺  Ge :ねずみ捕りが e にいるときに通行可能な(うるさくない)辺からなるGの全域部分グラフ ゲームの2部グラフ B(G, k)  左の頂点 ( f, v) : f は Gの面、 vはGの頂点  右の頂点 (e, C) : e は Gの辺、 CはGeの連結成分  e と f が接し、v ∈ C のとき    (f, v)と(e, C) を辺で結ぶ 3 7 1 10 f 4 8 e 5 9 ( f, 2) ( e, {2,3}) ( f, 3) ( f, 1) ( e, {1,4}) ( f, 4) ( f, 5) ( e, {5}) ( f, 6) ( e, {6,7}) ( f, 7) ( f, 8) ( e, {8,10}) ( f, 10) ( f, 9) ( e, {9})

B(G, k) 上でのゲーム実行 初期配置:  が 面 f0 を選び    が頂点 v0 を選ぶ 左頂点 (f0, v0) が決定 ラウンド: 現在の左頂点 (f, v)    が、(f, v) と隣接する 右頂点 (e, C) を選ぶ     (e を選べば C は自動的に決定)    が、 (e, C) と隣接する左頂点(f’, v’) を選ぶ     (f’は eに関して f と反対側の面)

B(G, k) の頂点の塗り分け 黒い頂点: 必勝 白い頂点: 必勝 仮定: G のどの頂点も次数 < k 黒い頂点:    必勝 白い頂点:    必勝 仮定: G のどの頂点も次数 < k 規則1:面f と 頂点 v が接していれば (f, v)を黒く塗る 規則2:辺 e と接する面を f1 , f2とし、CをGeのある連結成分とするとき、(e, C) と隣接する (f1, v) の形の左頂点がすべて黒、または(e, C)と隣接する (f2, v) の形の左頂点がすべて黒ならば (e, C)を黒く塗る 規則3:左頂点(f, v) と隣接する右頂点で黒いものがあれば(f, v)を黒く塗る すべての頂点が白い状態から出発して、規則1、2、3が適用できる限り適用を繰り返す。

必勝戦略 左の黒い頂点から:      の必勝戦略    規則2,3の伝播の向きを逆にたどり、常に黒い頂点にいるようにする。必ず規則1の頂点にたどりつく。 右の白い頂点から:    左の隣接頂点で白いものを選ぶ。 白い頂点がひとつでもあれば   必勝 すべての頂点が黒ならば   必勝

塗り分けアルゴリズムの効率 B(G, k) の頂点数: O(n2) 辺の数: O(n2) 黒色の伝播に各辺は高々一度使われる。 O(n2) 時間 注: 実際のアルゴリズムでは、面 f についてもねずみ捕りが fにいるときに通行可能な辺からなるグラフ Gf を考えて、2部グラフの頂点は、(f, C)、 C はGfの連結成分、とする。

=> G は幅 k 未満の bond carving を持つ 特徴づけの証明(やさしい方向) 幅 k 未満の刻み分割 →    の必勝戦略 仮定: G は幅 k 未満の刻み分割を持つ => G は幅 k 未満の bond carving を持つ Y Y X X

特徴づけの証明(やさしい方向) 幅 k 未満の bond carving Y Y X X

特徴づけの証明(やさしい方向) 幅 k 未満の bond carving Y Y X X

特徴づけの証明(やさしい方向) 幅 k 未満の bond carving Y Y X1 X2 X1 X2

特徴づけの証明(やさしい方向) 幅 k 未満の bond carving Y Y X1 X2 X1 X2

特徴づけの証明(難しい方向) 幅 k 未満の刻み分割の不在 => ねずみの必勝戦略 組み合わせ的な補題(Graph Minors. X ) 位相的な補題(Graph Minors. XI)

Tilt:一般のグラフに対する刻み分割の障害物 G における 位数 k の tilt :  B ⊆ 2V(G) で次の条件を満たすもの (1) | dG (X)| < k のとき、またそのときに限り、    X と V(G) \X のどちらか一方がB に属す。 (2)もし X, Y, Z ∈ B ならば X ∪ Y ∪ Z ≠ V(G) (3)各 v ∈ V(G) に対して {v}∈ B 定理(Robertson & Seymour 91) G の刻み幅が k 以上  G における 位数 k の tilt が存在する 証明 (<=) 容易(次ページ)     (=>) 難しい

G における位数 k のtilt が存在 => Gの刻み幅 ≧ k 易しい方向の証明 G における位数 k のtilt が存在 => Gの刻み幅 ≧ k 位数 k のtilt B  と 幅 k未満の刻み分割 Tが両方存在すると仮定して矛盾を導く B に基づいて、 Tの各辺に方向をつける。 Y Y Y X ∈ B Y X Y ∈ B X X

X ∪Y ∪ Z = V(X) で tiltの条件(2)と矛盾 易しい方向の証明(つづき) Tの葉と接続する辺はかならず中に向かう X Y Z 必ず入次数3のノードがある T X ∪Y ∪ Z = V(X) で tiltの条件(2)と矛盾

難しい方向 Gにおける位数 k のtilt が存在しない => Gの幅 k 未満の刻み分割が存在 帰納法による構成的証明。 帰納法のために、刻み分割の概念の一般化が必要。 そのまま実行すると指数時間かかる。

現在位置 刻み幅のねずみ捕りゲームによる特徴づけ 難しい方向 幅 k 未満の刻み分割の不在=> ねずみの必勝戦略 組み合わせ的補題 難しい方向    幅 k 未満の刻み分割の不在=> ねずみの必勝戦略   組み合わせ的補題     幅 k 未満の刻み分割の不在        => 位数 k の tilt の存在   位相的補題  平面グラフにおいては、tilt とねずみの必勝戦略は同じもの

Tilt = ねずみの必勝戦略 G: 平面グラフ B : Gにおける位数 k のtilt C : Gの長さ k 未満の双対閉路 (X, Y): カット Cによる V(G) の2分割 X と Y のちょうど一方がB に属す。 B に属さない方を、safeB (C )であらわす(安全サイド)。 C X Y

Tilt = ねずみの必勝戦略(続き) 平面グラフ G, 正整数 k: 固定 f: Gの面 Cf : ねずみ捕りが f にいるときに通行不能な辺からなる、長さGの双対閉路すべてからなる集合 補題  Gにおける位数 k のtilt B が存在するならば Gのすべての面 f に対して 解釈:ねずみ捕りがどの面にいても、ねずみはtilt B の処方する安全地帯にいることができる。 証明: ある面 f に対して補題の intersection が空ならば、 あるC1,C2,C3 に対してsafeB (C1 )∩ safeB (C2 ) ∩ safeB (C3 ) が空であることが示せる。 Tilt の条件(2)に矛盾。

特徴付け定理の理解=>アルゴリズムの改良 理論的な改良(o(n2) 幅決定、o(n3) 分割構成)はかなり難しそう。 組み合わせ的補題の難しい方向に、平面グラフの場合の全く新しい別証があれば突破口になるかもしれないが。 理解と、実験的知見にもとづいたヒューリスティックはいろいろ考えられる。主な目的:使用メモリ量の削減。

例:ねずみの極小戦略 ねずみの極大必勝戦略: ゲームの2部グラフの塗り分けから得られる白い頂点の集合 極小戦略: 各面に f に対して、 Gfの唯一の連結成分Cがあって、v ∈ Cに対する頂点 (f, v) のみを使用する。 実験的知見: ねずみ必勝のインスタンスでは(特にk が小さすぎて、楽に逃げ切れる場合) Gf は巨大コンポーネントを持つ傾向。  => ヒューリスティック: 各Gf の巨大コンポーネントが極小必勝戦略を構成するかどうかをチェックする。

今後の方向 特徴づけ定理の理解をさらに深める。 理解を、アルゴリズムの実際的な改良に利用していく。 できれば理論的な改良もかんがえたい。