点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日

Presentation on theme: "点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日"— Presentation transcript:

1 点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日
Thank you. Today I’d like to talk about “an extension of the disjoint paths problem” 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日

2 講演内容 イントロダクション 効率的に解けるケース 最短点素パス問題 演習 近年の発展（最大点素パス問題） ２点素パス問題
k点素パス問題 （Robertson-Seymour のアルゴリズム） その他の結果 最短点素パス問題 演習 近年の発展（最大点素パス問題）

3 イントロダクション 問題の定義 歴史 Thank you. Today I’d like to talk about “an extension of the disjoint paths problem”

4 点素パス問題 s3 s1 t1 t2 s2 t3 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) s3 s1 t1 t2 s2 t3

5 点素パス問題 s3 s1 t1 t2 s2 t3 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) s1 t1 s2 s3 t2 t3

6 点素（辺素）パス問題 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点（辺）を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素（辺素）なパス P1,…, Pk (Pi : si → ti ) s1 s1 t1 t1 s2 s2 t2 t2 様々な類似問題 有向グラフ or 無向グラフ 頂点対数 k が 定数 or 入力の一部 辺素パス or 点素パス etc. 多くの応用を持つ (例: VLSI の設計) The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on.

7 特殊ケース（１）： s-t 辺素パス問題 Input: 頂点対 (s, t)
Find: 辺素なパス P1,…, Pk (Pi : s → t ) X V - X 最大流アルゴリズムで多項式時間で解ける s t Menger の定理 （最大流・最小カット定理） k 本の辺素パスが存在 すべての s ∊ X ⊆V – t で δ(X) ≧ k The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on. X と V-X を結ぶ辺の数

8 特殊ケース（２）： t1 = t2 = ･･･ = tk の時
Input: 頂点対 (s1, t) ,…, (sk, t) Find: 辺素なパス P1,…, Pk (Pi : si → t ) s1 s2 最大流アルゴリズムで多項式時間で解ける s3 t sk The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on.

9 特殊ケース（２）： t1 = t2 = ･･･ = tk の時
Input: 頂点対 (s1, t) ,…, (sk, t) Find: 辺素なパス P1,…, Pk (Pi : si → t ) s1 s2 最大流アルゴリズムで多項式時間で解ける s3 s t sk The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on.

10 特殊ケース（２）： t1 = t2 = ･･･ = tk の時
Input: 頂点対 (s1, t) ,…, (sk, t) Find: 辺素なパス P1,…, Pk (Pi : si → t ) s1 s2 最大流アルゴリズムで多項式時間で解ける s3 s t sk 一般の場合にはうまくいかない The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on. s1 t1 s2 t2 s3 t3 結ぶ頂点の組を指定されるから難しい s t sk tk

11 目的：理論的計算量の解明 様々なバリエーションに対して 多項式時間で解けるか？ NP困難か？ より効率の良いアルゴリズムは？
The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on.

12 目的：理論的計算量の解明 様々なバリエーションに対して 多項式時間で解けるか？ NP困難か？ より効率の良いアルゴリズムは？
点素パス問題の計算量 有向グラフ 無向グラフ k : 定数 NP-困難 多項式時間 (平面グラフ) 多項式時間 (非巡回的) 多項式時間 線形時間 (平面グラフ) k : 変数 The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on. k : 頂点対数

13 各問題の帰着（演習） 無向点素パス問題 有向点素パス問題 無向辺素パス問題 有向辺素パス問題 下記のように帰着可能であることを示せ．
また，それぞれの帰着は平面性を保つか？ 無向点素パス問題 有向点素パス問題 無向辺素パス問題 有向辺素パス問題

14 辺素パスと点素パスの関係 辺素パス問題は線グラフ上の点素パス問題に帰着可能 辺素パス 点素パス s1 t1 s1 t1 s2 t2 s2
7 5 5 2 7 1 1 8 8 6 s2 3 4 t2 3 6 s2 4 t2 辺素パス 点素パス 定義 (線グラフ) 元のグラフの辺が線グラフの頂点に対応 元のグラフで同じ端点を持つ 線グラフで隣接

15 点素パス問題の計算量 辺素パス問題の計算量 有向グラフ 無向グラフ k : 定数 NP-困難 多項式時間 (平面グラフ)
多項式時間 (非巡回的) 多項式時間 線形時間 (平面グラフ) k : 変数 k : 頂点対数 辺素パス問題の計算量 有向グラフ 無向グラフ k : 定数 NP-困難 多項式時間 (非巡回的) 多項式時間 k : 変数 The disjoint paths problem, denoted DPP in this talk, is a classic and important problem in algorithmic graph theory, which is defined as follows. Suppose that we are given a graph and a collection of vertex pairs (s1, t1), …, (sk, tk). The problem is to find k vertex disjoint paths P1, …, Pk such that Pi is a path from si to ti for each i. For example, in this digraph, these two paths are a solution of the disjoint paths problem, the red path is from s1 to t1, the blue path is from s2 to t2, and they do not share any vertices. We can also consider the disjoint paths problem in an undirected graph. For example, in this graph, these two paths are a solution of the disjoint paths problem. Besides the theoretical interest of the problem, its importance arises from its practical applications, for example in VLSI-design. The disjoint paths problem has a number of variants, for example, the given graph is directed or undirected, the number of pairs k is a fixed constant or a part of the input, and the graph is planar and so on.

16 点素・辺素パス問題の歴史 最大最小定理 （s-t パス） Menger 最大流アルゴリズム Ford-Fulkerson
1927 最大最小定理 （s-t パス） Menger 1956 最大流アルゴリズム Ford-Fulkerson 1970s 頂点対数 k が入力の一部の時NP困難 Karp など 1980 k=2, 無向グラフの時のアルゴリズム Seymour, Thomassen, Shiloach k=2, 有向グラフの時NP困難 Even-Itai-Shamir 1994 k: 定数，平面有向グラフの時のアルゴリズム 1995 k: 定数，無向グラフの時のアルゴリズム Robertson-Seymour （点素のみ） Schrijver 近年 k: 入力の一部の時の近似アルゴリズム 特殊ケースに対するアルゴリズム など

17 ２点素パス問題 k点素パス問題 その他のケース
効率的に解けるケース ２点素パス問題 k点素パス問題 その他のケース Thank you. Today I’d like to talk about “an extension of the disjoint paths problem”

18 講演内容 イントロダクション 効率的に解けるケース 最短点素パス問題 演習 近年の発展（最大点素パス問題） ２点素パス問題
k点素パス問題 （Robertson-Seymour のアルゴリズム） その他の結果 最短点素パス問題 演習 近年の発展（最大点素パス問題）

19 無向点素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) k= 多項式時間アルゴリズム k：定数 多項式時間アルゴリズム k：変数 NP困難 Seymour, Thomassen, Shiloach (1980) Robertson-Seymour (1995) s1 t1 s2 s3 t2 t3 Karp (1975)

20 無向点素パス問題 難しいポイント カット条件 幾何的な条件 の両方を同時に扱う必要がある
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) k= 多項式時間アルゴリズム k：定数 多項式時間アルゴリズム k：変数 NP困難 難しいポイント Seymour, Thomassen, Shiloach (1980) カット条件 幾何的な条件 Robertson-Seymour (1995) s1 t1 s2 s3 t2 t3 の両方を同時に扱う必要がある Karp (1975)

21 無向点素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) k= 多項式時間アルゴリズム k：定数 多項式時間アルゴリズム k：変数 NP困難 Seymour, Thomassen, Shiloach (1980) Robertson-Seymour (1995) s1 t1 s2 s3 t2 t3 Karp (1975)

22 ２点素パス問題の解法 s1 t1 s2 t2 性質１ 平面グラフで s1, s2, t1, t2 が この順番に同じ面上 ２点素パス無し

23 ２点素パス問題の解法 s1 t1 s2 t2 性質１ 平面グラフで s1, s2, t1, t2 が この順番に同じ面上 ２点素パス無し
性質２ 小さいカットがあると問題を帰着可能 サイズ３ 連結 s1 t1 s2 t2 s1 t1 t2 s2 サイズ３

24 ２点素パス問題の解法 s1 t1 s2 t2 性質１ 平面グラフで s1, s2, t1, t2 が この順番に同じ面上 ２点素パス無し
性質２ 小さいカットがあると問題を帰着可能 サイズ３ 連結 s1 t1 s2 t2 s1 t1 t2 s2 サイズ３

25 ２点素パスの存在条件 ２点素パスが存在しない 性質２ の帰着を繰り返すと，性質１ の形になる s2 s1 s1 t1 t1 t2 s2 t2
サイズ３

26 ２点素パスの存在条件 定理 (Seymour, 1980) ２点素パスが存在しない 性質２ の帰着を繰り返すと，性質１ の形になる s2
t1 s2 t2 s1 t1 t2 s2 サイズ３

27 ２点素パスの存在条件 定理 (Seymour, 1980) ２点素パスが存在しない 性質２ の帰着を繰り返すと，性質１ の形になる s2
t1 s2 t2 s1 t1 t2 s2 サイズ３ ２点素パス問題は多項式時間で解ける カットを見つけるアルゴリズム 平面性判定アルゴリズム 現在： 線形時間 （Kapadia et al., 2010）

28 理解のために 平面的でない or 帰着を繰り返すと，性質１ の形 ２点素パスが存在しない 定理 命題
グラフが 「４点連結」 かつ 「平面的でない」 ２点素パスが存在 Shiloach (1980) の方針 平面的でない or をマイナーに持つ （Kuratowski の定理） K5 K3,3 縮約を繰り返すと部分グラフに持つ

29 理解のために 平面的でない or ４点連結 or 帰着を繰り返すと，性質１ の形 ２点素パスが存在しない 定理 命題
グラフが 「４点連結」 かつ 「平面的でない」 ２点素パスが存在 Shiloach (1980) の方針 平面的でない or をマイナーに持つ （Kuratowski の定理） K5 K3,3 s1 t1 ４点連結 s2 t2 or K5 K3,3 を使って繋げる

30 演習 平面性判定のアルゴリズムを用いて， 平面グラフで s1, s2, t1, t2 が をみたすかどうかを判定できることを示せ．
この順番に同じ面上

31 講演内容 イントロダクション 効率的に解けるケース 最短点素パス問題 演習 近年の発展（最大点素パス問題） ２点素パス問題
k点素パス問題 （Robertson-Seymour のアルゴリズム） その他の結果 最短点素パス問題 演習 近年の発展（最大点素パス問題）

32 無向点素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk)
パスが頂点を共有しない Input: 頂点対 (s1, t1),…, (sk, tk) Find: 点素なパス P1,…, Pk (Pi : si → ti ) k= 多項式時間アルゴリズム k：定数 多項式時間アルゴリズム k：変数 NP困難 Seymour, Thomassen, Shiloach (1980) Robertson-Seymour (1995) s1 t1 s2 s3 t2 t3 Karp (1975)

33 Robertson-Seymour のアルゴリズム
頂点対数 k：定数，無向グラフ 点素（辺素）パス問題に対する多項式時間アルゴリズム グラフマイナー理論に基づく 計算時間は O(n3) Graph Minors 13 (1995) 1983年～現在 23本の論文にわたる大理論 グラフ理論・アルゴリズムにおける大きな成果 Robertson & Seymour: Graph Minors 1 ～ 23 n: グラフの頂点数 k に依存する非常に大きな係数がかかる

34 Graph minors. I. Excluding a forest, JCTB, 35 (1983), 39-61
Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), Graph minors. III. Planar tree-width, JCTB, 36 (1984), 49-64 Graph minors. IV. Tree-width and well-quasi-ordering, JCTB, 48 (1990), Graph minors. V. Excluding a planar graph, JCTB, 41 (1986), Graph minors. VI. Disjoint paths across a disc, JCTB, 41 (1986), Graph minors. VII. Disjoint paths on a surface, JCTB, 45 (1988), Graph minors. VIII. A Kuratowski theorem for general surfaces, JCTB, 48 (1990), Graph minors. IX. Disjoint crossed paths, JCTB, 49 (1990), 40-77 Graph minors. X. Obstructions to tree-decomposition, JCTB, 52 (1991), Graph minors. XI. Circuits on a surface, JCTB, 60 (1994), Graph minors. XII. Distance on a surface, JCTB, 64 (1995), Graph minors. XIII. The disjoint paths problem, JCTB, 63 (1995), Graph minors. XIV. Extending an embedding, JCTB, 65 (1995), 23-50 Graph minors. XV. Giant steps, JCTB, 68 (1996), Graph minors. XVI. Excluding a non-planar graph, JCTB, 89 (2003), 43-76 Graph minors. XVII. Taming a vortex, JCTB, 77 (1999), Graph minors. XVIII. Tree-decompositions and well-quasi-ordering, JCTB, 89 (2003), Graph minors. XIX. Well-quasi-ordering on a surface, JCTB, 90 (2004), Graph minors. XX. Wagner's conjecture, JCTB, 92 (2004), Graph minors. XXI. Graphs with unique linkages, JCTB, 99 (2009), Graph minors. XXII. Irrelevant vertices in linkage problems, JCTB, 102 (2012), Graph minors. XXIII. Nash-Williams' immersion conjecture, JCTB, 100 (2010),

35 RSアルゴリズムの概要 グラフの木幅を計算 グラフの複雑さの指標 （1） 木幅≦（定数）： 動的計画法で解く
（1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む GM5 など ウォール

36 RSアルゴリズムの概要 グラフの木幅を計算 （1） 木幅≦（定数）： 動的計画法で解く
（1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む ウォール クリークマイナー 連結な 部分グラフ

37 RSアルゴリズムの概要 グラフの木幅を計算 （1） 木幅≦（定数）： 動的計画法で解く
（1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く GM22 の結果 ウォール クリークマイナー s1 連結な 部分グラフ t3 t1 s2 s3 t2

38 RSアルゴリズムの概要 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く 点素パスが見つかる 頂点を取り除く s1 t3 t1 以上を繰り返す s2 t2 s3

39 RSアルゴリズムの概要 グラフの木幅を計算 以上を繰り返す 合計 O(n3) 時間 O(n2) （1） 木幅≦（定数）： 動的計画法で解く
m: グラフの辺数 グラフの木幅を計算 O(n2) （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く O(n2) 点素パスが見つかる 頂点を取り除く O(m) 以上を繰り返す O(n) 回 合計 O(n3) 時間

40 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

41 木幅とは グラフがどれくらい木に近いか？ を表す指標 木幅 = １ 森 定義は置いておいて．．． 木幅= 3 木幅= 1 木幅= 2
グラフがどれくらい木に近いか？ を表す指標 木幅 = １ 森 定義は置いておいて．．． G G G G 木幅= 3 木幅= 1 木幅= 2 木幅= 2

42 木幅とは グラフがどれくらい木に近いか？ を表す指標 木幅 = １ 森 定義は置いておいて．．．
グラフがどれくらい木に近いか？ を表す指標 木幅 = １ 森 定義は置いておいて．．． “部品” を “木のように” 組み合わせることでグラフを作る 木幅 := “部品” の最大頂点数 – 1 G G G G 木幅= 3 木幅= 1 木幅= 2 木幅= 2

43 木幅の定義 (T, W) が G = (V, E) の 木分解 木幅= 2 T が木, W , 各枝に対して，Wt が存在して両端点を含む
t が T の上で t’ と t’’ の間にあるならば G T 木幅= 2

44 木幅の定義 (T, W) が G = (V, E) の 木分解 木幅= 2 T が木, W , 各枝に対して，Wt が存在して両端点を含む
t が T の上で t’ と t’’ の間にあるならば G T 木幅= 2

45 木幅の定義 (T, W) が G = (V, E) の 木分解 (T, W) の幅 := maxt |Wt| - 1
t が T の上で t’ と t’’ の間にあるならば G T 木幅= 2

46 演習 サイクルの木幅が 2 であることを示せ．

47 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

48 木幅小さい → 動的計画法 定理 （RS 1995, Arnborg-Proskurowski 1989 など） 木幅が w 以下のグラフ G=(V, E) において， k 点素パス問題は，(k+w)O(k+w) |V|O(1) 時間で解ける 部分問題 s1 G r1 r2 … で，s1, t1, s2, r1, r2, r3 が t1 どのように繋げるか，を列挙 r3 s2 例： ｛ s1 t1 , s2 r2 }, ｛ s1 r2 , s2 r3 }, … G T … … 木幅= 2

49 木幅小さい → 動的計画法 定理 （RS 1995, Arnborg-Proskurowski 1989 など） 木幅が w 以下のグラフ G=(V, E) において， k 点素パス問題は，(k+w)O(k+w) |V|O(1) 時間で解ける 部分問題 s1 G r1 r2 … で，s1, t1, s2, r1, r2, r3 が t1 どのように繋げるか，を列挙 r3 s2 葉から順に，繰り返し解く G T … … 木幅= 2

50 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

51 木幅大きい → ウォール 定理 （RS 1986） 任意の r に対してある f(r) が存在して以下が成立． 木幅が f(r) 以上の任意のグラフはサイズ r のウォールを含む Known results f(r) = , f(r) =Ω(r2 log r) G : planar f(r) = O(r) G : bounded genus f(r) = O(r) G : H-minor-free f(r) = cH・r G : K3,k-minor-free f(r) = 204k・r O(r5) (Robertson-Seymour-Thomas [1994], Diestel et al. [1999]) (Robertson-Seymour-Thomas [1994]) (Demaine et al. [2005]) (Demaine-Hajiaghayi [2008]) (Demaine et al. [2009])

52 木幅大きい → ウォール 定理 （RS 1986） 任意の r に対してある f(r) が存在して以下が成立． 木幅が f(r) 以上の任意のグラフはサイズ r のウォールを含む Known results f(r) = , f(r) =Ω(r2 log r) G : planar f(r) = O(r) G : bounded genus f(r) = O(r) G : H-minor-free f(r) = cH・r G : K3,k-minor-free f(r) = 204k・r G : H-minor-free f(r) = |V(H)|O(|E(H)|)・r G : general f(r) = 2 O(r5) (Robertson-Seymour-Thomas [1994], Diestel et al. [1999]) (Robertson-Seymour-Thomas [1994]) (Demaine et al. [2005]) (Demaine-Hajiaghayi [2008]) (Demaine et al. [2009]) Our results (Kawarabayashi-K [2012]) O(r2 log r)

53 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

54 ほぼ平面的なウォール （2） tw(G) > （定数） なら大きなウォールを含む （2-1） 内部がほぼ平面的な大きなウォールを含む
（2-1） 内部がほぼ平面的な大きなウォールを含む （2-2) 大きなクリークマイナーを含む ウォール内部がほぼ平面的 def （高々 9k2 個の頂点を取り除くと） 対角の頂点を結ぶ２本の点素パスがウォール内部に取れない

55 目標： ほぼ平面的な大きなウォール 大きなクリークマイナー 大きなウォール def ウォールがほぼ平面的 （定数個頂点除くと） が無い

56 目標： ほぼ平面的な大きなウォール 大きなクリークマイナー 大きなウォール def ウォールがほぼ平面的 （定数個頂点除くと） が無い

57

58 ケース (2) の場合分け （2） tw(G) > （定数） なら大きなウォールを含む
（2-1） 内部がほぼ平面的な大きなウォールを含む （2-2) 大きなクリークマイナーを含む ポイント がたくさんあると，クリークマイナーを作れる

59 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

60 少しだけ各ステップの説明 グラフの木幅を計算 GM22 の結果 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む GM22 の結果 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

61 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

62 クリークマイナーの処理 サイズ 2k のクリーク C があるとする ターミナルから C へ 2k 個の点素パスが存在
（本当はクリークマイナーだが簡単のため） s1 s1 t1 t3 t3 t1 s2 s2 t2 t2 s3 s3 サイズ ≦ 2k - 1 Menger の定理

63 クリークマイナーの処理 サイズ 2k のクリーク C があるとする ターミナルから C へ 2k 個の点素パスが存在
（本当はクリークマイナーだが簡単のため） s1 s1 t1 t3 t3 t1 s2 s2 t2 t2 s3 s3 サイズ ≦ 2k - 1 Menger の定理

64 クリークマイナーの処理 サイズ 2k のクリーク C があるとする ターミナルから C へ 2k 個の点素パスが存在
（本当はクリークマイナーだが簡単のため） s1 s1 t1 t3 t3 t1 s2 s2 t2 t2 s3 s3 サイズ ≦ 2k - 1 無関係！ Menger の定理

65 少しだけ各ステップの説明 グラフの木幅を計算 以上を繰り返す （1） 木幅≦（定数）： 動的計画法で解く
（１） 木幅とは？ （２） 木幅小さい →動的計画法 グラフの木幅を計算 （３） 木幅大きい →ウォール （1） 木幅≦（定数）： 動的計画法で解く （2） 木幅 > （定数）： 大きなウォールを含む （４） ほぼ平面的？ （2-1） 内部がほぼ平面的な大きなウォールを含む （2-2） 大きなクリークマイナーを含む 中央の頂点を取り除く （５） (2-1) の正当性 （６） (2-2) の正当性 点素パスが見つかる 頂点を取り除く 以上を繰り返す

66 講演内容 イントロダクション 効率的に解けるケース 最短点素パス問題 演習 近年の発展（最大点素パス問題） ２点素パス問題
k点素パス問題 （Robertson-Seymour のアルゴリズム） その他の結果 最短点素パス問題 演習 近年の発展（最大点素パス問題）

67 その他の結果（１） 平面的 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 観察 t2 t1
s3 tk s1 t3 s2 平面的 sk

68 その他の結果（１） 平面的 平面的 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける
観察 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 定理 (Suzuki-Akama-Nishizeki, 1988) グラフが平面的で，ターミナルが高々2つの面の周上のとき， 点素パス問題は O(n) 時間で解ける t2 t1 t1 t2 s3 tk tk s1 s2 sk s3 s1 t3 t3 s2 平面的 平面的 sk

69 その他の結果（２） 平面的 平面的 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける
観察 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 定理 (Okamura-Seymour, 1981) グラフが平面的で，ターミナルが1つの面の周上， オイラー条件を満たすとき，辺素パス問題は t2 t1 s3 t1 t2 s3 tk tk s1 s1 t3 t3 s2 平面的 s2 平面的 sk sk

70 その他の結果（２） 平面的 平面的 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける
観察 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 定理 (Okamura-Seymour, 1981) グラフが平面的で，ターミナルが1つの面の周上， オイラー条件を満たすとき，辺素パス問題は 多項式時間で解ける 各頂点に接続する 需要＋供給 の枝数が偶数 現在：O(n) 時間 (Wagner-Weihe [1993]) t2 t1 s3 t1 t2 s3 tk tk s1 s1 t3 t3 s2 平面的 s2 平面的 sk sk

71 その他の結果（２） グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける
観察 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 定理 (Okamura-Seymour, 1981) グラフが平面的で，ターミナルが1つの面の周上， オイラー条件を満たすとき，辺素パス問題は 多項式時間で解ける 各頂点に接続する 需要＋供給 の枝数が偶数 現在：O(n) 時間 (Wagner-Weihe [1993]) 定理 (Frank, 1985) グラフが平面的で，ターミナルが1つの面の周上， 内点が偶数次数のとき，辺素パス問題は多項式時間で解ける 現在：O(n) 時間 (Weihe [1999])

72 その他の結果（２） 難しいポイント カット条件 幾何的な条件 の両方を同時に扱う必要がある どれも幾何的な条件が扱いやすい形
観察 グラフが平面的で，ターミナルが高々1つの面の周上のとき， 点素パス問題は多項式時間で解ける 定理 (Okamura-Seymour, 1981) グラフが平面的で，ターミナルが1つの面の周上， 難しいポイント オイラー条件を満たすとき，辺素パス問題は 多項式時間で解ける どれも幾何的な条件が扱いやすい形 各頂点に接続する 需要＋供給 の枝数が偶数 現在：O(n) 時間 カット条件 幾何的な条件 (Wagner-Weihe [1993]) 定理 (Frank, 1985) の両方を同時に扱う必要がある グラフが平面的で，ターミナルが1つの面の周上， 内点が偶数次数のとき，辺素パス問題は多項式時間で解ける 現在：O(n) 時間 (Weihe [1999])

73 演習 枝集合 s1t1, s2t2, …, siti をもつグラフを H とする． グラフが平面的，ターミナルが1つの面の周上，
Demand graph 枝集合 s1t1, s2t2, …, siti をもつグラフを H とする． 定理 (Okamura-Seymour, 1981) グラフが平面的，ターミナルが1つの面の周上， オイラー条件 (G+H の次数がすべて偶数) を満たすとき， 辺素パスが存在 カット条件が成立 任意のカットに対して， G の枝数 ≧ H の枝数 「オイラー条件」を除くと，この関係が成り立たなくなることを示せ． 「1つの面の周上」という条件を除くと，成り立たなくなることを示せ．

74 第一部，第二部 まとめ 点素パス問題の難しさ カット条件 幾何的な条件 未解決問題 の両方を同時に扱う必要がある
第一部，第二部 まとめ 点素パス問題の難しさ 未解決問題 有向平面グラフ上の辺素パス問題 有向平面グラフ上の点素パス問題のFPT ３点素パスの存在の特徴づけ カット条件 幾何的な条件 の両方を同時に扱う必要がある

75

76 例題 点素パスを見つけよ s2 s1 s3 s4 t1 t3 t2 t4

77 例題２ 点素パスを見つけよ s3 s2 s4 s1 t2 t4 t3 t1