点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 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 のアルゴリズム） その他の結果 最短点素パス問題 演習 近年の発展（最大点素パス問題）

辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Find: 辺素なパス P1,…, Pk (Pi : si → ti ) 辺素パス問題の計算量 (既存の結果) 無向グラフ 有向グラフ k : 定数 多項式時間 NP-困難 OPEN (平面グラフ) k : 変数 (Robertson-Seymour) 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. 点素だと P

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) s1 t1 =t4 s2 t3 s3 t2 s4 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.

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) s1 t1 =t4 s2 t3 s3 t2 s4 様々な種類の問題 無向グラフ or 有向グラフ k が 入力の一部 or 定数 辺素パス or 点素パス 混雑度（congestion） c を許す 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. 決定問題に帰着 各辺を通るパスは高々 c 本

点素（辺素）問題関連の論文（１） A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2, J. Chuzhoy and S. Li, FOCS 2012. Routing in Undirected Graphs with Constant Congestion, J. Chuzhoy, STOC 2012. Approximation Algorithms and Hardness of Integral Concurrent Flow, P. Chalermsook, J. Chuzhoy, A. Ene, S. Li, STOC 2012. Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2, L. Seguin-Charbonneau and F. B. Shepherd, FOCS 2011. Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem, K. Kawarabayashi and Y. Kobayashi, STOC 2011. Shortest non-crossing walks in the plane, J. Erickson, A. Nayyeri, SODA 2011.

点素（辺素）問題関連の論文（２） Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions, M. Andrews, FOCS 2010. Flow-Cut Gaps for Integer and Fractional Multiflows, C. Chekuri, F. B. Shepherd, Weibel, SODA 2010. The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs, K. Kawarabayashi and Y. Kobayashi, SODA 2010. A Nearly Linear Time Algorithm for the Half Integral Parity Disjoint Paths Packing Problem, K. Kawarabayashi, B. Reed, SODA 2009. Finding disjoint paths in expanders deterministically and online, N. Alon and M. Capalbo, FOCS 2008. A Nearly Linear Time Algorithm for the Half Integral Disjoint Paths, K. Kawarabayashi, B. Reed, SODA 2008.

論文を読む前に（読むために） 既存研究のまとめ 最大辺素パス問題の難しさ 近似アルゴリズムの基本方針 なぜ congestion？ 今後の展開

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 O(log1/2-ε n)-近似不可能 [一般グラフ] O(log1/(c+1)-ε n)-近似不可能 [混雑度=c] (Andrews et al. 2005) 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. n : 頂点数 r -近似アルゴリズム： OPT / r 本のパスを出力 最適値

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 O(log1/2-ε n)-近似不可能 [一般グラフ] O(log1/(c+1)-ε n)-近似不可能 [混雑度=c] O(n1/2)-近似アルゴリズム [一般グラフ] O(n1/c)-近似アルゴリズム [混雑度=c] (poly log(n))-近似アルゴリズム [連結度：高] (Andrews et al. 2005) (Chekuri et al. 2006) (Srinviasan 1997) 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. (Rao-Zhou 2009) (乱択) n : 頂点数 r -近似アルゴリズム： OPT / r 本のパスを出力 最適値

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 O(log1/2-ε n)-近似不可能 [一般グラフ] O(log1/(c+1)-ε n)-近似不可能 [混雑度=c] O(n1/2)-近似アルゴリズム [一般グラフ] O(n1/c)-近似アルゴリズム [混雑度=c] (poly log(n))-近似アルゴリズム [連結度：高] O(n3/7)-近似アルゴリズム [混雑度=2] (Andrews et al. 2005) (Chekuri et al. 2006) (Srinviasan 1997) 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. (Rao-Zhou 2009) (乱択) ~ (乱択) (Kawarabayashi, K. 2011) poly log n を無視 各辺を通るパスは高々 2本

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 O(log1/2-ε n)-近似不可能 [一般グラフ] O(log1/(c+1)-ε n)-近似不可能 [混雑度=c] O(n1/2)-近似アルゴリズム [一般グラフ] O(n1/c)-近似アルゴリズム [混雑度=c] (poly log(n))-近似アルゴリズム [連結度：高] O(n3/7)-近似アルゴリズム [混雑度=2] O(poly log(n))-近似アルゴリズム [混雑度=14] (Andrews et al. 2005) (Chekuri et al. 2006) (Srinviasan 1997) 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. (Rao-Zhou 2009) (乱択) ~ (乱択) (Kawarabayashi, K. 2011) (Chuzhoy, 2012) (乱択)

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 （平面グラフ） グラフが平面的，オイラー的でも NP-困難 O(log n)-近似アルゴリズム [平面, 混雑度=2] O(1)-近似アルゴリズム [平面, 混雑度=4] O(1)-近似アルゴリズム [平面, 混雑度=2] (Chekuri et al. 2004) (Chekuri et al. 2006) 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. (Seguin-Charbonneau-Shepherd, 2011) n : 頂点数

最大辺素パス問題 Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 既存研究 （平面グラフ） グラフが平面的，オイラー的でも NP-困難 O(log n)-近似アルゴリズム [平面, 混雑度=2] O(1)-近似アルゴリズム [平面, 混雑度=4] O(1)-近似アルゴリズム [平面, 混雑度=2] O(log2 n)-近似アルゴリズム [平面, オイラー的] O(log n)-近似アルゴリズム [平面, オイラー的] (Chekuri et al. 2004) (Chekuri et al. 2006) 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. (Seguin-Charbonneau-Shepherd, 2011) (Kleinberg 2005) (Kawarabayashi, K. 2010) n : 頂点数

最大辺素パス問題の難しさ Input: 頂点対 (s1, t1),…, (sk, tk) Maximize: ♯{Pi | 互いに辺素なパス} (Pi : si → ti ) 辺素パス問題の難しさ カット条件 幾何的な条件 の両方を同時に扱う必要がある ＋ どの頂点対を結ぶか，を選ぶ難しさ c.f. All-or-nothing flow problem

近似アルゴリズムの基本方針 最適解の上界が必要 (i =1, …, k) 上界 OPT r 倍 出力   si -ti パス全体 上界 OPT   (i =1, …, k) r 倍 P 出力         r -近似アルゴリズム： OPT / r 本のパスを出力 最適値

なぜ congestion? congestion 1 だと近似が難しい 上界 OPT 出力 (i =1, …, k) s1 s2 s3   上界 sk OPT t1 t2 t3 tk   出力   (i =1, …, k) P        

今後の展開（私見） さらなる近似比の改善，脱ランダム化 緩和のない（congestion 1）のケース 新たな上界の構成（違うLP定式化）

まとめ 点素パス問題： カット条件 幾何的な条件 を同時に扱う問題 様々な未解決問題 近年は最大化問題が注目されている