点素パス問題に対するアルゴリズム
小林 佑輔
東京大学 大学院情報理工学系研究科
組合せ最適化セミナー 2012 年 7月 13日
近年の発展
最大点素（辺素）パス問題
講演内容


イントロダクション
効率的に解けるケース
 ２点素パス問題
 k点素パス問題
（Robertson-Seymour のアルゴリズム）
 その他の結果



最短点素パス問題
演習
近年の発展（最大点素パス問題）
辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Find: 辺素なパス P1,…, Pk (Pi : si → ti )

辺素パス問題の計算量 (既存の結果)
k : 定数
無向グラフ
有向グラフ
多項式時間
NP-困難
OPEN (平面グラフ)
NP-困難
(Robertson-Seymour)
k : 変数
NP-困難
点素だと P
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}
s1
t1 =t4
s2
t3
s3
s4
t2
(Pi : si → ti )
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}
s1
(Pi : si → ti )
t1 =t4
s2
t3
s3
s4

t2
様々な種類の問題




無向グラフ or 有向グラフ 決定問題に帰着
k が 入力の一部 or 定数
各辺を通るパス
辺素パス or 点素パス
は高々 c 本
混雑度（congestion） 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-edgeconnected 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 | 互いに辺素なパス}

既存研究
 O(log1/2-ε n)-近似不可能
 O(log1/(c+1)-ε n)-近似不可能
[一般グラフ]
(Pi : si → ti )
(Andrews et al. 2005)
[混雑度=c]
n : 頂点数
r -近似アルゴリズム： OPT / r 本のパスを出力
最適値
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}

既存研究
 O(log1/2-ε n)-近似不可能
 O(log1/(c+1)-ε n)-近似不可能
 O(n1/2)-近似アルゴリズム
 O(n1/c)-近似アルゴリズム
 (poly log(n))-近似アルゴリズム
[一般グラフ]
(Pi : si → ti )
(Andrews et al. 2005)
[混雑度=c]
[一般グラフ]
(Chekuri et al. 2006)
[混雑度=c]
(Srinviasan 1997)
[連結度：高]
(乱択)
(Rao-Zhou 2009)
r -近似アルゴリズム： OPT / r 本のパスを出力
最適値
n : 頂点数
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}

既存研究
 O(log1/2-ε n)-近似不可能
 O(log1/(c+1)-ε n)-近似不可能
 O(n1/2)-近似アルゴリズム
 O(n1/c)-近似アルゴリズム
 (poly log(n))-近似アルゴリズム

~
[一般グラフ]
(Andrews et al. 2005)
[混雑度=c]
[一般グラフ]
(Chekuri et al. 2006)
[混雑度=c]
(Srinviasan 1997)
[連結度：高]
(乱択)
(Rao-Zhou 2009)
O(n3/7)-近似アルゴリズム (乱択) [混雑度=2]
poly log n を無視
(Pi : si → ti )
(Kawarabayashi, K. 2011)
各辺を通るパス
は高々 2本
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}

既存研究
 O(log1/2-ε n)-近似不可能
 O(log1/(c+1)-ε n)-近似不可能
 O(n1/2)-近似アルゴリズム
 O(n1/c)-近似アルゴリズム
 (poly log(n))-近似アルゴリズム
~
(Pi : si → ti )
[一般グラフ]
(Andrews et al. 2005)
[混雑度=c]
[一般グラフ]
(Chekuri et al. 2006)
[混雑度=c]
(Srinviasan 1997)
[連結度：高]
(乱択)
(Rao-Zhou 2009)

O(n3/7)-近似アルゴリズム (乱択) [混雑度=2]

O(poly log(n))-近似アルゴリズム [混雑度=14]
(乱択)
(Kawarabayashi, K. 2011)
(Chuzhoy, 2012)
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}

既存研究 （平面グラフ）
 グラフが平面的，オイラー的でも NP-困難
 O(log n)-近似アルゴリズム [平面, 混雑度=2]
 O(1)-近似アルゴリズム
[平面, 混雑度=4]
 O(1)-近似アルゴリズム
[平面, 混雑度=2]
(Pi : si → ti )
(Chekuri et al. 2004)
(Chekuri et al. 2006)
(Seguin-Charbonneau-Shepherd, 2011)
n : 頂点数
最大辺素パス問題
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}

既存研究 （平面グラフ）
 グラフが平面的，オイラー的でも NP-困難
 O(log n)-近似アルゴリズム [平面, 混雑度=2]
 O(1)-近似アルゴリズム
[平面, 混雑度=4]
 O(1)-近似アルゴリズム
[平面, 混雑度=2]
(Pi : si → ti )
(Chekuri et al. 2004)
(Chekuri et al. 2006)
(Seguin-Charbonneau-Shepherd, 2011)
O(log2 n)-近似アルゴリズム [平面, オイラー的]
 O(log n)-近似アルゴリズム [平面, オイラー的]

(Kleinberg 2005)
(Kawarabayashi, K. 2010)
n : 頂点数
最大辺素パス問題の難しさ
Input: 頂点対 (s1, t1),…, (sk, tk)
Maximize: ♯{Pi | 互いに辺素なパス}
(Pi : si → ti )
辺素パス問題の難しさ
 カット条件
 幾何的な条件
の両方を同時に扱う必要がある
＋
どの頂点対を結ぶか，を選ぶ難しさ
c.f. All-or-nothing flow problem
近似アルゴリズムの基本方針

最適解の上界が必要
si -ti パス全体
P
上界
(i =1, …, k)
r倍
OPT
出力
r -近似アルゴリズム： OPT / r 本のパスを出力
最適値
なぜ congestion?
s1
s2
s3
congestion 1 だと近似が難しい
上界
sk
t1 t2
t3
OPT
tk
出力
P
(i =1, …, k)
今後の展開（私見）
さらなる近似比の改善，脱ランダム化
 緩和のない（congestion 1）のケース
 congestion 2
グラフの条件に
 新たな上界の構成（違うLP定式化）

まとめ

点素パス問題：
 カット条件
 幾何的な条件
を同時に扱う問題

様々な未解決問題

近年は最大化問題が注目されている

こちら - 名古屋大学大学院工学研究科量子工学専攻

EUROCOMB `17 Vienna