最小節点ランキング全域木問題について 豊橋技術科学大学知識情報工学系 増山繁 科研費特定領域研究「新世代の計算限界ーその解明と打破ー｣ 平成18年度第1回全体会議 平成18年6月2１日(水)ー22日(木) 九州大学ベンチャービジネスラボラトリ3階セミナー室

節点ランキング 5 1 3 2 4 同じラベルを持つ節点を結ぶどの路上にも、そのラベルより大きな値の For example. For each path between any two vertices with the same rank, there exists at least one vertex whose rank is greater than the rank of these two vertices. 同じラベルを持つ節点を結ぶどの路上にも、そのラベルより大きな値の ラベルを持つ節点が必ずあるような、節点への自然数によるラベル付け

最小節点ランキング問題 4 3 2 1 グラフGの最小節点ラン キングにおける最大 ラベルの値 与えられたグラフの節点ランキングのうちで最大ランクを最小にする ような節点ランキングをみつける問題

最小節点ランキング全域木問題 1 3 2 4 1 2 3 Gの全域木Tのうち、　　　　を最小にするものを求める 問題

センサネットワークにおけるデータ収集プロセッサの配置 1 2 3 The minimum vertex ranking spanning tree problem is defined as follows: Given a graph G Find a spanning tree of G whose vertex ranking is minimum. Processor　for Data　collection sensor

最小節点ランキング全域木問題に関係ある問題 節点ランキング問題 辺ランキング問題 最小辺ランキング全域木問題

節点ランキングと辺ランキング 節点ランキング 辺ランキング 1 2 3 4 1 2 5 3 4 節点ランキングの定義で｢節点｣とある ところを｢辺｣と変えたもの

最小辺ランキング全域木問題 1 2 3

最小節点ランキング全域木問題に関係ある問題 節点ランキング問題 　一般のグラフ・・・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]

（＊ 最適値を求めるのではなく，yes / no を求める問題．） MVRSTのNP困難性の証明 [宮田敬三(TUT), 増山繁(TUT), 中山慎一(徳島大), 趙亮（京大）, to Appear in DAM] 3次元マッチング問題（NP完全） 決定問題版＊のMVRST 多項式時間帰着可能 （＊ 最適値を求めるのではなく，yes / no を求める問題．）

３次元マッチング問題 の問題例 x = (X,Y,Z,S) 問題例の作成 ３次元マッチング問題 の問題例 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 ３DMの説明を口頭でもっと説明する X,Y、Zを図でくくる X Y Z n＝2 x1 x2 y1 y2 z1 z2

帰着のためのgadget

帰着のためのgadget

帰着されたグラフ中の 4-rankable spanning tree

計算量： O(|V|・(|V|+|E|)) 近似アルゴリズム 与えられたグラフをG=(V,E)とする。 1. V　の各要素vに対して、ｖからGの他のすべての節点に対する最短路を求める。 　　　　　　　　　　　　 但し、d(u,v)はu、vの距離 2. となるsを選び、ｓから幅優先探索を行い木Tを得、それに対し　　　　を求める。 計算量： O(|V|・(|V|+|E|)) 近似率 （ 　　はGの全域木の直径の最小値）

区間グラフ上でMVRSTを で求めるアルゴリズム 中山慎一、増山繁：　２００３ 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個含む部分グラフ、…の順に動的計画法を用いて構成していく。

直径を求める 1 2 3 (※)区間の右端が最も左にある区間に対応する節点を 区間の左端が最も右にある区間に対応する節点を とし、　　　　　　をそれぞれ左端、右端とする直径P*を取る。 (※)直径P*に属さないすべての節点はP*の節点に枝で結ばれている。

直径P*に属さないすべての節点はP*の節点に枝で結ばれていることの説明 P*上にない節点ｖに対応する区間I=[x,y]に対して、 　　　　　　、または、　　　　　　　の少なくとも一方は成り立つ。 一方、 内の点は全てP*上の点に対応する区間に 含まれることに注意すると、区間IはP*上の点に対応するい ずれかの区間I’と共有点を持つ。I’に対応する点をv’とすると、 ｖとv’は枝で結ばれている。 (※)以下のいずれも起こりえない。 Ｙ ｘ Ｙ ｘ

パスに関する節点ランキング [補題1 ] 節点数 n 個のパス P のランキングχ(P) は log n +1 である． 1 2 3 4

直径を求める 1 2 3 1 2 1 V’１:直径上の節点と1点のみで接する直径外の節点 V’２:直径上の節点と２点以上で接する直径外の節点

V’ だけの場合 V’ 1 2 1 2 3 1 直径 P* のランキング数χ(P*) と等しい ランキング数の全域木 T を構成できる． 2

区間グラフの最小節点 ランキング全域木 ［補題2］区間グラフGにおいて．Gの直径P*のランキン 　　　　　グ数をχ（P*)とする．構成された全域木Tの最小 節点ランキング数χ(T)は， χ (T)≦χ（P*)+1 である.

アルゴリズムの方針 G2 G1 直径P*のランキング数χ(P*)と等しい ランキング数の全域木 T が構成できるか？

アルゴリズムの方針

アルゴリズムの方針 1 2 3 Max{1,1,1,1,3}+1 =4

アルゴリズムの方針

アルゴリズムの方針 1 2 Max{2,2,2}+1 =3

動的計画法 G2 G1 直径のランキング数χ(P*)と等しい ランキング数の全域木 T が構成できるか？

P*上における2連続節点 からなる部分グラフ G[v ,v ] j j+1 この場合のみ χ (T)＝χ（P*)+1 (1) (2) v v j j+1

P*上における2連続節点 からなる部分グラフ G[v ,v ] j j+1 v’ v’ a b (1) (2) v v j j+1

P*上における2連続節点 からなる部分グラフ G[v ,v ] j j+1 v’ v’ a b (1) (1) V’ v” 1 V’ 2 (2) (1) (1) v v (1) (2) j j+1

P*上における2連続節点 からなる部分グラフ G[v ,v ] j j+1 v’ v’ a b (1) V’ 1 V’ 2 (2) (1) (2) v v (3) j j+1

P*上における3連続節点 からなる部分グラフ この場合のみ χ (T)＝χ（P*)+1 G[v ,v ] j j+2 v’ v’ v’ 1 2 V’ 1 V’ 2 v (3) (4) v j+1 v v v (1) (2) (1) j-1 j+3 j j+2

P*上における3連続節点 からなる部分グラフ G[v ,v ] j j+2 v’ v’ v’ 1 2 (2) (1) v” V’ 1 V’ 2 v j+1 v v (3) (1) (2) (1) (4) j j+2

P*上における3連続節点 からなる部分グラフ G[v ,v ] j j+2 v’ v’ v’ 1 2 (2) (1) V’ v” 1 V’ 2 v (3) (4) j+1 v v (1) (2) (1) j j+2

2連結グラフ v’ v’ V’ v” V’ v v v G[v ,v ] (2) (1) (3) (4) (1) (2) (1) j+1 j

動的計画法 G2 G1 χ(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 3 2

計算量 Step 1. グラフの直径を求める O(n2) 時間 Step 2. 直径に属さない節点がV1, V2 のいづれであるか調べる

外平面グラフ上でMVRSTを多項式時間で求めるアルゴリズム 中山慎一、増山繁：　2006 IEICE Trans. Information　and Systems

外平面グラフ上のMVRST 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 (1) (2) (3) Given a outerplanar graph G, we find an minimum vertex ranking spanning tree like this.

アルゴリズムの方針 外周上の連続する節点からなる部分グラフ Gi ,i=1,・・・,l, を求める ある節点 v に各部分グラフ Gi ,i=1,・・・,l, における最小節点ランキング全域木を接続する．その場合，各部分グラフ Gi における最大ランクを 　　とすると，節点 v には ランク k+1　を割り当てる

木の最小節点ランキング v T1 T2 T3 T5 T4 Max{χ(T1),χ(T2),χ(T3), χ(T4) ,χ(T5) }+1 A path from a vertex of a component to a vertex of another component obviously go through v. Then, by assigning the maximum rank of these components plus 1 to v, the condition of vertex ranking of the tree is satisfied. (However, the resulting vertex ranking is not necessarily the minimum one.) Max{χ(T1),χ(T2),χ(T3), χ(T4) ,χ(T5) }+1 =Max{1,1,1,1,3}+1 =4

木の最小節点ランキング v Next, by removing this vertex, the tree is divided into these components.

木の最小節点ランキング 1 2 v 2 1 The vertex ranking of each subtree is 2. Then, the condition of vertex ranking is satisfied by assigning 3 to this vertex. By repeating this process for each vertex, we can find the minimum vertex ranking of a tree. Based on this observation, we develop an algorithm as follows. Max{2,2,2}+1 =3 1 2 1

全域木 3 2 4 1 5 (1) (4) (2) (3) 6 15 14 7 Like tree, we divide a outerplanar graph to some subgraphs and find each minimum vertex ranking spanning tree in each subgraph. After that, we join the minimum vertex ranking spanning trees to a vertex. In this case, we join these trees to vertex 7. 8 13 12 9 10 11

部分グラフ G[14:7] 部分グラフ G[7:13] 部分グラフ 2 4 1 5 6 15 14 部分グラフ G[7:13] 7 8 13 12 9 10 11 It is important that how we select subgraphs because the number of subgraphs is exponential. We here construct subgraphs based on consecutive vertices on the boundary of the exterior face of G. G[x:y] is a subgraph of G induced by a vertex set consisting of all vertices form x to y in anticlockwise order on the boundary of the exterior face of G. As a result, we consider subgraphs induced by 2-consecutive vertices, 3-consecutive vertices, until n-consecutive vertices. G[x:y] : Gの外周上で節点xからvまで反時計回りにたどっていって出会う節点によって誘導されるGの部分グラフ.

χT(7 : G)=4 部分グラフ χT(v : G) : 節点vに最大ランクを割り振るという条件のもとでの最小節点全域木の最大ランク 3 2 4 1 5 6 (1) (1) (1) (3) 15 (2) (2) (1) (1) 14 7 (4) (1) (1) (1) (2) 8 (1) (3) 13 χT(7 : G)=4 12 9 10 11 On each subgraph, we must assign the largest rank to a vertex. Then, we use the following notation. χT(v : G) is the vertex ranking number of an minimum vertex ranking spanning tree in G under the condition that a vertex v is assigned the largest rank. In this case, we assign the largest rank to vertex 7. In order to satisfy the condition of vertex ranking, we must assign rank 4 to vertex 7. χT(v : G) : 節点vに最大ランクを割り振るという条件のもとでの最小節点全域木の最大ランク

全域木 G[10:4] G[4:9] χT(4 : G)=4 3 2 1 4 5 (4) (3) 15 6 (2) 14 7 (1) 13 In the previous case, we assigned the largest rank to vertex 7. If we must assign the largest rank to vertex 4, we find minimum vertex ranking spanning trees in these subgraphs under the condition that a vertex 4 is assigned the largest rank. Like this, for each vertex v, we divide a graph into subgraphs, find each minimum vertex spanning tree in each subgraph under the condition that a vertex v is assigned the largest rank. 8 13 12 G[4:9] 9 10 11

全域木 3 2 4 1 5 G[1:7] (1) (2) (4) (3) 6 15 14 7 This is another step. We pay attention to vertex 1. In this case, subgraphs G[1:7] and G[8:1] are considered. For each subgraph, a spanning tree is constructed under the condition that a vertex 1 is assigned the largest rank. For vertex 1, we need to find spanning trees in each pair of subgraphs G[1,x] and G[x,1], x=2, … n-1. 8 13 12 9 10 11 G[8:1]

全域木 G[9:1] 3 2 4 1 5 (1) (2) (4) (3) 6 15 14 7 Thus, the next step, subgraphs G[1:8] and G[9:1] are considered. In this case, vertex 1 is assigned rank 4. 8 13 12 G[1:8] 9 10 11

全域木 G[10:1] G[1:9] χT(1 : G)=4 3 2 1 4 5 (3) 15 6 (2) 14 7 (1) 13 8 12 And, next, subgraphs G[1:9] and G[10:1] are considered. In this case, vertex 1 is assigned rank 3. このように，各部分グラフ　G[1,x] and G[x,1], x=2, … n-1　における全域木が求まっていれば， 節点１に最大ランクを割り当てる条件での最小節点ランキング全域木が求まる． しかし，そのためにはsubgraphs G[1,x] and G[x,1], x=2, … n-1　における全域木を求めていなければならない． ここで，外平面グラフの特徴を利用することになる． 外平面グラフの部分グラフは，また外平面グラフである． よって，再帰的に全域木を求めていくことが可能となる． 8 13 G[1:9] 12 9 10 11

全域木 3 2 4 1 5 (1) (2) (3) 6 15 14 7 8 13 12 9 10 11

部分グラフ i x u y u+1 v z w i+l (b) Type 2 (a) Type 1 部分グラフ G[x,y:z,w] ここでは，部分グラフを二つのタイプに分類できる． 一つは，外周上の連続する節点集合からなる部分グラフである． もう一つは，外周上の二つの連続する節点集合からなる部分グラフである． Type 1，Type 2　共に，外平面グラフである． v z w i+l 部分グラフG[i,i+l] またはG[i,i:i,i+l] (b) Type 2 (a) Type 1

外平面グラフにおける，最小節点ランキング [　補題　]　グラフ G は2重連結外平面グラフとする．Gの部分グラフと最小節点全域木ランキングについて次の式が成り立つ． 外平面グラフGにおいて，Gの部分グラフも外平面グラフなので， 部分グラフの最小節点ランキング全域木を再帰的に求めていくことが可能となる． そのために必要な補題が次の通りである． この補題を基に再帰的にアルゴリズムを構成できる．

アルゴリズムの概要 Step 1.各部分グラフ G[x,y;z,w], x,y,z,w=1,・・・,n に　　　　　　　　　対し， Type 1(外周上の節点が連続)かType 2 (外周上の節点が２つの連続した部分に分かれている)であるか判定する． Step 2. 各部分グラフ G[x,y;z,w] に含まれる節点数が増加する順に，以下の式を用い部分グラフの最小辺ランキングを求める． 先の補題を用いて，部分グラフの最小節点ランキング全域木を再帰的に求めることが可能である． しかし，我々のアルゴリズムでは再帰は用いずに，ボトムアップに次のようにアルゴリズムを構成した．

(2) (1) (2) (1) ２つの連続した節点により誘導された 部分グラフ 3 2 1 4 5 15 6 14 7 13 8 12 9 10 11 12 13 14 15 1 2 3 4 5 6 (2) (1) まず最初に，2節点からなる各部分グラフについて，最小節点ランキング全域木を求める． 2節点間に辺が存在すれば，その辺を用いて節点ランク2の全域木が構成できる． 2節点間に辺が存在しなければ，全域木は構成できないのでランク∞を代入する． (2) (1)

(2) (2) (1) (1) ３つの連続した節点により誘導された 部分グラフ 3 2 1 4 5 15 6 14 7 13 8 12 9 10 11 12 13 14 15 1 2 3 4 5 6 (1) (2) (1) (2) 次に，3節点からなる各部分グラフについて，最小節点ランキング全域木を求める． 部分グラフが　Type 1，Type 2　のいずれかを調べ，連結であるならば 節点ランク2の全域木が構成でき，非連結であるならば全域木は構成できないので∞を代入する．

(3) (3) (2) (2) (1) (1) ４つの連続した節点により誘導された 部分グラフ 3 2 1 4 5 15 6 14 7 13 8 9 10 11 12 13 14 15 1 2 3 4 5 6 (1) (3) (2) (1) (2) (3) 続いて，4節点からなる各部分グラフについて，最小節点ランキング全域木を求める． 既に求まっている2節点，3節点からなる部分グラフの最小節点ランキング全域木の値を基に 先に示した補題の式を用い最小節点全域木ランキングを求める．

(2) (1) (3) ６つの連続した節点により誘導された 部分グラフ 3 2 1 4 5 15 6 14 7 13 8 12 9 11 10 11 12 13 14 15 1 2 3 4 5 6 (2) (1) (3) このように，5節点からなる部分グラフ，6節点からなる部分グラフと ｎ節点から部分グラフまで同様の処理を行う． この例のように，節点７に最大ランクを割り当てる条件での全域木を求めるのに， 既に求まっている2節点からなる部分グラフにおける全域木を用いて求めることになる．

最後のStep 3 2 (2) (1) 4 1 5 (1) (3) 6 15 14 7 最終的には，1　から　n-1　個の節点からなる部分グラフの最小節点ランキング全域木の情報を基に ｎ個の節点からなる部分グラフの最小節点ランキング全域木を求めることになる． 8 13 12 9 10 11

計算量 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に対して多項式時間アルゴリズムを持つほかのグラフのクラスを求めること

ご清聴ありがとうございました。