最小節点ランキング全域木問題について

最小節点ランキング全域木問題
について
豊橋技術科学大学知識情報工学系
増山繁
科研費特定領域研究「新世代の計算限界ーその解明と打破ー｣
平成18年度第1回全体会議
平成18年6月2１日(水)ー22日(木)
九州大学ベンチャービジネスラボラトリ3階セミナー室
節点ランキング
2
3
5
1
3
4
2
2
同じラベルを持つ節点を結ぶどの路上にも、そのラベルより大きな値の
ラベルを持つ節点が必ずあるような、節点への自然数によるラベル付け
最小節点ランキング問題
3
1
1
1
3
4
2
 (G) :
2
グラフGの最小節点ラン
キングにおける最大
ラベルの値
与えられたグラフの節点ランキングのうちで最大ランクを最小にする
ような節点ランキングをみつける問題
最小節点ランキング全域木問題
1
3
2
1
1
1
2
3
1
1
2
2
1
1
4
1
Gの全域木Tのうち、  (T )を最小にするものを求める
問題
センサネットワークにおけるデー
タ収集プロセッサの配置
1
1
2
2
3
1
2
2
1
1
1
1
1
2
2
1
1
1
Processor for
Data collection
1
1
1
sensor
最小節点ランキング全域木問題
に関係ある問題



節点ランキング問題
辺ランキング問題
最小辺ランキング全域木問題
節点ランキングと辺ランキング
節点ランキング
1
3
辺ランキング
1
3
1
1
3
4
5
2
1
2
3
4 1
2
4
2
節点ランキングの定義で｢節点｣とある
ところを｢辺｣と変えたもの
最小辺ランキング全域木問題
1
2
3
1
1
2
1
最小節点ランキング全域木問題
に関係ある問題

節点ランキング問題
一般のグラフ・・・NP困難[Pothen, 1988]
多項式時間アルゴリズム
木 [Schaffer, 1990]
区間グラフ，置換グラフ，台形グラフ[Deogun et. al., 1999]
k-木グラフ [Bodlaender et. al., 1998]
 辺ランキング問題
一般のグラフ・・・NP困難[Lam, Yue, 1998]
多項式アルゴリズム
木
[Torre et. al., 1995]
最小節点ランキング全域木問題
に関係ある問題

最小辺ランキング全域木問題
NP困難である
近似アルゴリズムが開発されている
[Makino, Uno and Ibaraki, 2001]
MVRSTのNP困難性の証明
[宮田敬三(TUT), 増山繁(TUT), 中山慎一(徳島大), 趙亮（京大）,
to Appear in DAM]
3次元マッチング問題（NP完全）
多項式時間帰着可能
＊
決定問題版のMVRST
（＊最適値を求めるのではなく，yes / no を求める問題．）
問題例の作成
３次元マッチング問題の問題例 x = (X,Y,Z,S)
決定問題版のMVRST の問題例
f(x) = (G=(V,E) , k)
（χ(T)≦k を満たす全域木Tが存在するか？）
問題例の作成
ここでは決定問題版のMVRST の代わりに
その部分クラスである
4-rankable spanning tree問題（4RST)：
f(x) = (G=(V,E) , ４)
χ(T)≦k を満たす全域木Tが存在するか？
を使用
３次元マッチング問題の問題例 x=(X,Y,Z,S)
入力：
X = {x1,x2} ，Y = {y1,y2} ，Z = {z1,z2} ：互いに素な集合
S = { s1=(x1,y1,z1) , s2=(x2,y2,z2) , s3=(x1,y1,z2) } ： S⊆X×Y×Z
s1
s2
s3
m＝3
x 1 x 2 y 1 y 2 z1 z2
X
Y
Z
n＝2
帰着のためのgadget
帰着のためのgadget
s3
s1 s 2
x1 x2 y
1 y2 z 1
2z
帰着されたグラフ中の
4-rankable spanning tree
近似アルゴリズム
与えられたグラフをG=(V,E)とする。
1. V の各要素vに対して、ｖからGの他のすべての節点
に対する最短路を求める。
L(u)  maxvV d (u, v) 但し、d(u,v)はu、vの距離
2. L(s)  maxuV L(u) となるsを選び、ｓから幅優先
探索を行い木Tを得、それに対し  (T ) を求める。
計算量： O(|V|・(|V|+|E|))
Ds / 2  1

近似率 :　log2 ( Ds  1)  1
（Ds はGの全域木の
直径の最小値）
区間グラフ上でMVRSTを O(n ) で
求めるアルゴリズム
3
中山慎一、増山繁：２００３
IEICE Trans. Fundamentals
区間グラフ
区間ダイアグラム
区間グラフ
区間グラフにおいて、MVRSTを解く多項式
時間アルゴリズムを可能にしている性質
直径P*をうまくとると、P*上にないすべての節点
はP*上のいずれかの節点と枝で結ばれている。
 長さ4以上の閉路は必ず弦を含む(区間グラフは
Chordal graph）。

区間グラフにおいて、MVRSTを解く多項式
時間アルゴリズムを可能にしている性質
直径P*をうまくとると、P*上にないすべての節点
はP*上のいずれかの節点と枝で結ばれている。
 長さ4以上の閉路は必ず弦を含む(区間グラフは
Chordal graph）。

アルゴリズムの方針
Step 1. グラフのある条件を満たす直径を求める
Step 2. 直径に属さない節点を直径に属する
節点に辺で接続して全域木を構成する
Step 3. 全域木構成に使う辺を決定するため，
動的計画法を用いて部分グラフの
ランキングを求める
その際、P*上の節点を1個含む部分グラフ、2
個含む部分グラフ、…の順に動的計画法を用い
て構成していく。
直径を求める
v r min
1
2
3
1
2
1
(※)区間の右端が最も左にある区間に対応する節点を v r
min
l
区間の左端が最も右にある区間に対応する節点を
vmax
r
l
とし、vmin , vmaxをそれぞれ左端、右端とする直径P*を取る。
(※)直径P*に属さないすべての節点はP*の節点に枝で結ばれている。
直径P*に属さないすべての節点はP*の
節点に枝で結ばれていることの説明
P*上にない節点ｖに対応する区間I=[x,y]に対して、
l
r
y

v
の少なくとも一方は成り立つ。
max
vmin  xr 、または、
l
一方、[vmin , vmax ] 内の点は全てP*上の点に対応する区間に
含まれることに注意すると、区間IはP*上の点に対応するい
ずれかの区間I’と共有点を持つ。I’に対応する点をv’とすると、
ｖとv’は枝で結ばれている。
(※)以下のいずれも起こりえない。
ｘ
Ｙ
v
r
vmin
l
vmax
r
min
ｘ
l
max
v
Ｙ
パスに関する節点ランキング
[補題1 ] 節点数 n 個のパス P のランキングχ(P) は
log n +1 である．
1
3
2
1
4
2
3
1
直径を求める
1
2
3
1
2
1
V’１:直径上の節点と1点のみで接する直径外の節点
V’２:直径上の節点と２点以上で接する直径外の節点
V’2 だけの場合
1
2
1
2
3
V’2
1
直径 P* のランキング数χ(P*) と等しい
ランキング数の全域木 T を構成できる．
区間グラフの最小節点
ランキング全域木
［補題2］区間グラフGにおいて．Gの直径P*のランキン
グ数をχ（P*)とする．構成された全域木Tの最小
節点ランキング数χ(T)は，
χ (T)≦χ（P*)+1
である.
アルゴリズムの方針
G1
G2
直径P*のランキング数χ(P*)と等しい
ランキング数の全域木 T が構成できるか？
アルゴリズムの方針
アルゴリズムの方針
2
1
3
1
1
2
Max{1,1,1,1,3}+1
=4
アルゴリズムの方針
アルゴリズムの方針
1
1
1
2
1
2
1
1
1
2
Max{2,2,2}+1
=3
動的計画法
G1
G2
直径のランキング数χ(P*)と等しい
ランキング数の全域木 T が構成できるか？
P*上における2連続節点
からなる部分グラフ
G[vj ,vj+1]
この場合のみ
χ (T)＝χ（P*)+1
(1)
vj
(2)
vj+1
P*上における2連続節点
からなる部分グラフ
G[vj ,vj+1]
v’a
(1)
vj
v’b
(2)
vj+1
P*上における2連続節点
からなる部分グラフ
G[vj ,vj+1]
v’a
(1)
(1)
v’b
V’1
v”
(1)
vj (1)
V’2
(2)
(1)
(2) v
j+1
P*上における2連続節点
からなる部分グラフ
G[vj ,vj+1]
v’a
v’b
(1)
(2)
(3)
(1)
V’1
V’2
(1)
vj
(2)
vj+1
P*上における3連続節点
からなる部分グラフ
この場合のみ
χ (T)＝χ（P*)+1
G[vj ,vj+2]
v’1
v’
v’2
V’1
V’2
(3)
vj-1
v j (1)
vj+1
(2)
(1) v j+2
(4)
vj+3
P*上における3連続節点
からなる部分グラフ
G[vj ,vj+2]
v’1
(1)
v’
(1)
v’2
v”
(1)
V’2
(2)
(3)
vj (1)
vj+1
(1)
(2)
V’1
(1) v j+2 (4)
P*上における3連続節点
からなる部分グラフ
G[vj ,vj+2]
(1)
v”
(3)
v’1
(1)
v’
(2)
(1)
v’2
V’1
V’2
(2)
vj (1)
vj+1
(2)
(1) v j+2
(4)
2連結グラフ
G[vj ,vj+2]
(1)
v”
(3)
v’1
(1)
v’2
V’1
(1)
(1)
(2)
V’2
(2)
vj (1)
vj+1
(2)
(1) v j+2
(4)
動的計画法
G1
G2
χ(G)=MAX{χ(G1), χ(G2)}+1
=MAX{ 2, 3}+1
=4
動的計画法
G1
G2
χ(G)=MAX{χ(G1), χ(G2)}+1
=MAX{ 2, 2}+1
=3
結果
1
1
1
1
1
1
1
1
1
2
1
3
2
1
計算量
Step 1. グラフの直径を求める
O(n2) 時間
Step 2. 直径に属さない節点がV1, V2 のいづ
れであるか調べる
O(n) 時間
Step 3. 動的計画法を用いて部分グラフのラン
キングを求める
O(n3) 時間
外平面グラフ上でMVRSTを多項
式時間で求めるアルゴリズム
中山慎一、増山繁： 2006
IEICE Trans. Information and Systems
外平面グラフ上のMVRST
5
6
(1)
4
3
2
1
(1) (1) (1) (3)
15
(2)
(2)
(1)
7 (1)
(1)
8
(1) (1) (2)
9 10
11
(1)
12
(1)
13
14
アルゴリズムの方針
① 外周上の連続する節点からなる部分グラフ
Gi ,i=1,・・・,l, を求める
② 各部分グラフ Gi ,i=1,・・・,l, の最小節点全域木を求
める
③ ある節点 v に各部分グラフ Gi ,i=1,・・・,l, における
最小節点ランキング全域木を接続する．その場合，
各部分グラフ Gi における最大ランクを k  Max { (Gi )}
i 1,l
とすると，節点 v にはランク k+1 を割り当てる
木の最小節点ランキング
1
T1
v
T5
2
1
3
1
1
2
1
T2
1
4
T3
T
1 4
Max{χ(T1),χ(T2),χ(T3),
χ(T4) ,χ(T5) }+1
=Max{1,1,1,1,3}+1
=4
木の最小節点ランキング
v
木の最小節点ランキング
1
1
2
2
1
2
v
1
1
1
1
Max{2,2,2}+1
=3
全域木
5
6
(2)
4
3
2
1
(1) (1) (1) (3)
15
(2)
(1)
(1)
7 (4)
(1)
8
(2) (1) (3)
9 10
11
(1)
12
(1)
13
14
部分グラフ
5 4
6
3 2
部分グラフ G[14:7]
1
15
14
7
8
部分グラフ G[7:13]
9 10 11
12
13
G[x:y] : Gの外周上で節点xからvまで反時計回りにたどって
いって出会う節点によって誘導されるGの部分グラフ.
部分グラフ
3 2
4
1
5
6
(1) (1)(1) (3)
15
(2)
(2)
(1)
(1) 14
7 (4)
χT(7 : G)=4
(1)
8
(1)
(2) (1) (3)
9 10 11 12
(1)
13
χT(v : G) : 節点vに最大ランクを割り振るという条件のもと
での最小節点全域木の最大ランク
全域木
χT(4 : G)=4
5
6
(1)
4
3
G[10:4]
2
1
(4) (1) (1) (3)
15
(2)
(2)
(1)
7 (1)
(1)
8
G[4:9]
(1) (1) (2)
9 10
11
(1)
12
(1)
13
14
全域木
G[1:7]
5
6
(1)
4
3
2
1
(1) (1) (1) (4)
15
(2)
(2)
(1)
7 (1)
(1)
8
(2) (1) (3)
9 10
11
(1)
14
(1)
13
12
G[8:1]
全域木
5
6
(1)
4
3
G[9:1]
2
1
(1) (1) (1) (4)
15
(2)
(2)
(1)
7 (1)
(1)
8
G[1:8]
(1) (2) (3)
9 10
11
(1)
12
(1)
13
14
全域木
χT(1 : G)=4
5
6
(1)
4
3
2
G[10:1]
1
(1) (1) (1) (3)
15
(2)
(2)
(1)
7 (1)
(1)
8
G[1:9]
(1) (1) (2)
9 10
11
(1)
12
(1)
13
14
全域木
5
6
(1)
4
3
2
1
(1) (1) (1) (3)
15
(2)
(2)
(1)
7 (1)
(1)
8
(1) (1) (2)
9 10
11
(1)
12
(1)
13
14
部分グラフ
i
u+1 u
x
y
部分グラフ
G[x,y:z,w]
v
部分グラフG[i,i+l]
またはG[i,i:i,i+l]
i+l
(a) Type 1
z
w
(b) Type 2
外平面グラフにおける，最小節点ラ
ンキング
[ 補題 ] グラフ G は2重連結外平面グラフとする．Gの部分
グラフと最小節点全域木ランキングについて次の式が成り立
つ．
T (G )  min{min{max{T (v : G[v, u ]),
1 v  n 1u  n
T (v : G[u  1, v])}}}
アルゴリズムの概要
Step 1.各部分グラフ G[x,y;z,w], x,y,z,w=1,・・・,n に
対し， Type 1(外周上の節点が連続)かType 2 (外周上の
節点が２つの連続した部分に分かれている)であるか判定
する．
Step 2. 各部分グラフ G[x,y;z,w] に含まれる節点数が増加する順
に，以下の式を用い部分グラフの最小辺ランキングを求
める．
T (G )  min{min{max{T (v : G[v, u ]),
1 v  n 1u  n
T (v : G[u  1, v])}}}
２つの連続した節点により誘導された
部分グラフ
5
4
3
2
1
15
6
(2)
14
7
(2)
8
(1)
9 10
13
11
12
３つの連続した節点により誘導された
部分グラフ
5
(1)
4
3
2
1
15
6
14
7 (1)
(2)
(2)
8
13
(1)
9
10
11
12
４つの連続した節点により誘導された
部分グラフ
4
5
6
(1)
(3)
3
2
1
15
(1)
14
7 (3)
(2)
(2)
8
(1)
9
13
10
11
12
６つの連続した節点により誘導された
部分グラフ
5
6
7
4
3
2
1
15
(1)
(1) (2)
14
(3)
(2)
8
13
(1)
9
10
11
12
最後のStep
5
6
(1)
4
3
2
1
(1) (1) (1) (3)
15
(2)
(2)
(1)
7 (1)
(1)
8
(1)
9
(1) (2)
11
10
(1)
12
(1)
13
14
計算量
Step 1.部分グラフ G[x,y;z,w], x,y,z,w=1,・・・,n の
数が O(n4) 個存在する．各部分グラフに対し
Type 1かType 2 であるか判定するのにO(1)
時間かかるので，全体として O(n4) 時間かか
る．
Step 2. O(n4) 個の各部分グラフに対し，最小節点全
域木ランキングを求めるのに O(n) 時間かか
る．よって，全体としてO(n５) 時間かかる．
今後の課題

MVRSTに対して多項式時間アルゴリズムを
持つほかのグラフのクラスを求めること
ご清聴ありがとうございました。

Download Report