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

最短点素パス問題 Thank you. Today I’d like to talk about “an extension of the disjoint paths problem”

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

最短点素パス問題 (Min-Sum) Input: 頂点対 (s1, t1),…, (sk, tk)， 各辺 e の長さ l(e) Find: 点素パス P1,…, Pk (Pi : si → ti ) s.t. パスの合計長さ最小 自然な最適化問題 ほとんどの場合で計算複雑度が未解決 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.

最短点素パス問題 (Min-Sum) Input: 頂点対 (s1, t1),…, (sk, tk)， 各辺 e の長さ l(e) Find: 点素パス P1,…, Pk (Pi : si → ti ) s.t. パスの合計長さ最小 s1 自然な最適化問題 ほとんどの場合で計算複雑度が未解決 t1 s2 t2 s3 t3 解決済のケース NP困難な点素パス問題に対応 NP困難 最小費用流問題に帰着できる場合 多項式時間 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上 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. 多項式時間 （Colin de Verdière & Schrijver, 2008）

参考：点素パス問題の計算量 有向グラフ 無向グラフ k : 定数 NP-困難 多項式時間 (平面グラフ) 多項式時間 (非巡回的) 線形時間 (平面グラフ) k : 変数 k : 頂点対数

Min-Sum 点素パス問題の難しさ 点素パス問題 難しさ ： 頂点対の繋ぎ方が指定されている 難しさ ： 頂点対の繋ぎ方が指定されている 解法の鍵 ： 繋げるか否かに関係ない頂点を取り除く 組み合わせるのが困難 最小費用流問題 難しさ ： 費用が最小である保証が必要 解法の鍵 ： フローの多面体的表現 ＋ 双対概念 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.

現状： 最小費用流問題 ＋ グラフの特殊性の利用 Min-Sum 点素パス問題の難しさ 点素パス問題 難しさ ： 頂点対の繋ぎ方が指定されている 解法の鍵 ： 繋げるか否かに関係ない頂点を取り除く 組み合わせるのが困難 最小費用流問題 難しさ ： 費用が最小である保証が必要 解法の鍵 ： フローの多面体的表現 ＋ 双対概念 多項式時間で解ける場合 最小費用流問題に帰着できる場合 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上 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. （Colin de Verdière & Schrijver, 2008） 現状： 最小費用流問題 ＋ グラフの特殊性の利用

現状： 最小費用流問題 ＋ グラフの特殊性の利用 Min-Sum 点素パス問題の難しさ 点素パス問題 難しいポイント 難しさ ： 頂点対の繋ぎ方が指定されている 解法の鍵 ： 繋げるか否かに関係ない頂点を取り除く カット条件 幾何的な条件 + 最適性 組み合わせるのが困難 最小費用流問題 難しさ ： 費用が最小である保証が必要 解法の鍵 ： フローの多面体的表現 ＋ 双対概念 を同時に扱う必要がある 多項式時間で解ける場合 最小費用流問題に帰着できる場合 平面グラフで，s1,..., sk が同一面上，t1,..., tk が同一面上 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. （Colin de Verdière & Schrijver, 2008） 現状： 最小費用流問題 ＋ グラフの特殊性の利用

Min-Sum 点素パス問題に対する成果 成果：特殊ケースの解決 (K. and Sommer, 2009) 成果：特殊ケースの解決 無向平面グラフで ターミナルが 高々２つの面上 にあるときk=2 の Min-Sum 点素パス問題は 多項式時間 で解ける s1 s1 s2 t1 t1 t2 t2 s2 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 s2 t2 t1 s1 t1 s2 t2 Colin de Verdière & Schrijver 最小費用流問題

Min-Sum 点素パス問題の難しさ カット条件 + 最適性 幾何的な条件 を同時に扱う必要がある これまで紹介： + 最適性 を同時に扱う必要がある これまで紹介： これから話す： 「幾何的な条件」 が扱いやすいケース 「カット条件」 が扱いやすいケース J. Erickson and A. Nayyeri: Shortest non-crossing walks in the plane, SODA 2011

Shortest non-crossing walks Input: 頂点対 (s1, t1),…, (sk, tk)， 各辺 e の長さ l(e) Find: 合計長さ最小の walk P1,…, Pk (Pi : si → ti ) s.t. walk は互いにクロスしない s1 t1 s1 t2 s1 t2 s2 t2 s2 t1 s2 t1 OK NG NG 例 s1 s2 t1 t2

Shortest non-crossing walks Input: 頂点対 (s1, t1),…, (sk, tk)， 各辺 e の長さ l(e) Find: 合計長さ最小の walk P1,…, Pk (Pi : si → ti ) s.t. walk は互いにクロスしない s1 t1 s1 t2 s1 t2 s2 t2 s2 t1 s2 t1 OK NG NG 例 s1 s2 t1 t2

ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける 例 h = 2 obstacle 定理 (Erickson-Nayyeri, 2009) ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける O(h2) 例 obstacle s1 s2 t1 t2 h = 2

ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける 関連研究 例 h = 2 obstacle 定理 (Erickson-Nayyeri, 2009) ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける O(h2) 関連研究 h = 1 のとき 個別に最短路求めるだけ h = 2 のとき O(n log k) 時間 (Takahashi-Suzuki-Nishizeki, 1992) h : 一般 のとき NP-hard (Bastert-Fekete, 1998) 例 obstacle s1 s2 t1 t2 h = 2

ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける 細かい注意 例 h = 2 obstacle 定理 (Erickson-Nayyeri, 2009) ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける O(h2) 細かい注意 ターミナルと Obstacle の間を 他のパスが通らないものとする 例 obstacle s1 s2 t1 t2 h = 2

ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける 方針 obstacle 定理 (Erickson-Nayyeri, 2009) ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける O(h2) 方針 いくつかの walk をとり，それらに沿って切り開く S’T’-walks どのペアも同じ面上 s2 s2 s1 s1 t3 t3 t2 t2 t1 s3 t1 s3

演習 obstacle 各 i に対して， si と ti が共通の面の周上のとき， Shortest non-crossing walks が多項式時間で 解けることを示せ． （計算時間はとりあえず気にしない）

どのようなパスで切り開くか？ 最適解の部分解 の候補

どのようなパスで切り開くか？ 最適解の部分解 の候補 同じ homotopy class の中で最短のもの 最適解の部分解 の候補 同じ homotopy class の中で最短のもの 定義 2つの walk α, β が同じ homotopy class ∃連続写像 h: [0,1]×[0,1] → （平面 - obstacle） s.t. h(0, ･ ) = α, h(1, ･ ) = β h(･ , 0) = α(0) = β(0), h(･ , 1) = α(1) = β(1) α α obstacle β β 同じ 違う

最適解の性質 観察 Shortest non-crossing walks の最適解において 各 walk は，同じ homotopy class の中で最短 略証 α が同じ homotopy class の中で最短だとすると， 合計長さが短くできるので． s3 s3 P3 t3 P3 t3 P2 P2 s2 t2 s2 t2 s1 α t1 s1 α t1 P1

最適解の性質 同じ homotopy class の中で最短のパスが 最適解に使われるパスの候補 観察 Shortest non-crossing walks の最適解において 各 walk は，同じ homotopy class の中で最短 略証 α が同じ homotopy class の中で最短だとすると， 合計長さが短くできるので． 同じ homotopy class の中で最短のパスが s3 最適解に使われるパスの候補 s3 P3 t3 P3 t3 P2 P2 s2 t2 s2 t2 s1 α t1 s1 α t1 P1

アルゴリズム すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP 1 すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP ２ Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ STEP ３ 得られた ST-walks の中で最短のものを出力

アルゴリズム すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 （1） 個数を 2 で抑える O(h2) STEP 1 すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP ２ Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ （2） どう計算するか？ STEP ３ 得られた ST-walks の中で最短のものを出力

補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない

Ω = {ω1, … , ωk}： 最適な ST-walks 補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない s2 t3 この補題を認めると．．． s1 最短パス σ1, … , σh-1 を用いて h 個の obstacle faces を繋ぐ σ1 t2 σ2 t1 s3

Ω = {ω1, … , ωk}： 最適な ST-walks 補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない s2 t3 この補題を認めると．．． s1 最短パス σ1, … , σh-1 を用いて h 個の obstacle faces を繋ぐ σ1 t2 σ2 t1 s3 σi を用いて切り開き，σi , si, ti の 接続関係を表すグラフ Π を作成 s2 t3 σ1 σ2 s1 t2 Π は高々 2 通り O(h2) t1 σ2 σ1 s3 Π

2O(h) × (2O(h)) 補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない s2 t3 この補題を認めると．．． s1 最短パス σ1, … , σh-1 を用いて h 個の obstacle faces を繋ぐ 2O(h) × (2O(h)) O(h) σ1 t2 σ2 t1 弦の引き方 並行枝の本数 s3 σi を用いて切り開き，σi , si, ti の 接続関係を表すグラフ Π を作成 σ1 s2 s1 t1 s3 t2 σ2 t3 Π は高々 2 通り O(h2) Π

演習 頂点数 n のサイクルが与えられたときに， 互いに交わらない弦の引き方が 2O(n) 通り であることを示せ．

walks の復元 Π から walk を復元したい homotopy class は決まるので σ1 σ2

walks の復元 Π から walk を復元したい homotopy class は決まるので σ1 σ2 例えば，s3→σ1→σ2→t3 なら， グラフ 3 つを貼りあわせて最短路 計算時間： 2O(h) n Π

アルゴリズム（再掲） すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 （1） 個数を 2 で抑える O(h2) STEP 1 すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP ２ Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ （2） どう計算するか？ STEP ３ 得られた ST-walks の中で最短のものを出力

簡単のため，「2k 回しかクロスしない」 を示す 補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない あとは補題を示せばよい． 簡単のため，「2k 回しかクロスしない」 を示す 準備 X(σ, Ω) : σ が交差する walk を順に並べた index 列 X(σ, Ω) の部分列が even どの index も偶数回現れる

主張１ X(σ, Ω) は非空で even な部分列を持たない σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks X(σ, Ω) : σ が交差する walk を順に並べた index 列

X(σ, Ω) は非空で even な部分列を持たない 主張１ X(σ, Ω) は非空で even な部分列を持たない 証明 even な部分列を持つと，walks を繋ぎ直して より短い ST-walks が得られるので矛盾． 同じ色を繋ぎかえる 1 → 4 5 → 8 9 → 12 3 1 8 3 σ 1 1 5 3 2 2 6 4 4 2 7 4 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks X(σ, Ω) : σ が交差する walk を順に並べた index 列

X(σ, Ω) は非空で even な部分列を持たない 主張１ X(σ, Ω) は非空で even な部分列を持たない 証明 even な部分列を持つと，walks を繋ぎ直して より短い ST-walks が得られるので矛盾． 同じ色を繋ぎかえる 1 → 4 5 → 8 9 → 12 3 1 8 3 3 σ 1 1 5 2 2 6 4 4 2 7 4 3 1 8 3 3 σ 1 1 5 演習 この繋ぎかえで，クロスが生じないことを示せ 2 2 6 4 4 2 7 4

演習 主張２ を証明せよ 主張２ 長さ 2k 以上の X(σ, Ω) は，非空で even な部分列を持つ σ : ある2点間の最短パス σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks X(σ, Ω) : σ が交差する walk を順に並べた index 列 X(σ, Ω) の部分列が even どの index も偶数回現れる

簡単のため，「2k 回しかクロスしない」 を示す 補題 σ : ある2点間の最短パス Ω = {ω1, … , ωk}： 最適な ST-walks 各 ωi は σ と高々 22h-2 回しかクロスしない 簡単のため，「2k 回しかクロスしない」 を示す 主張１ X(σ, Ω) は非空で even な部分列を持たない 主張２ 長さ 2k 以上の X(σ, Ω) は，非空で even な部分列を持つ 主張１，主張２より，示された．

アルゴリズム（再掲） すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 （1） 個数を 2 で抑える O(h2) STEP 1 すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP ２ Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ （2） どう計算するか？ STEP ３ 得られた ST-walks の中で最短のものを出力

アルゴリズム（再掲） ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける 定理 (Erickson-Nayyeri, 2009) アルゴリズム（再掲） ターミナルが h 個の面の周上にあるとき， 2 n log k の計算時間で解ける （1） 個数を 2 で抑える O(h2) O(h2) STEP 1 すべての homotopy class の組合せに対し， 最短の S’T’-walks Ω’ を計算 STEP ２ Ω’ で切り開いたグラフで，残りのターミナルを繋ぐ （2） どう計算するか？ STEP ３ 得られた ST-walks の中で最短のものを出力

まとめ：最短点素パス問題 自然な最適化問題 ほとんどの場合で計算複雑度が未解決 現状 カット条件 幾何的な条件 のどちらかが扱いやすい場合のみ