Branch-length とtree-length(計算機科学の理論とその応用)

Branch-length

と

tree-length

群馬大学大学院工学研究科 梅澤香織 (K.Umezawa)

群馬大学工学部情報工学科 山崎浩一 (K.Yamazaki)

Computer

Science,

Gunma\cdot University

概要

Branch-decomposition 上のパラメータ branch-length を定義し, branch-length が tree-decomposition 上で定義される tree-length と一致することを示す. キーワード :tree-decomposition, tree-length, brani-decompositIon, branch-length

1

はじめに

Branch-width と tree-width _は, 古くから盛 んに研究されているグラフパラメータである. そ の理由の1つに一般のグラフ上では $NP$_完全な 問題も branch-width または tree-width を制限 することで多項式時間で解けることが挙げられ る $[1, 8]$

.

Branch-width はbranch-decomposition上で 定義され, tree-width は tree-decomposition 上 で定義される. Branch-width に着目したア) レ ゴリズムの多くは branch-decomposition を用 いており, それらの計算量は branch-width に 深く依存している. 同様に tree-width に着目 したアルゴリズムの多くは tree-decomposition を用い, それらの計算量は tree-width に深く 依存している. Branch-decomposition はハイ パーグラフやマトロイドへの一般化が自然に行 えるという利点を持つ. 一方tree-decomposition は直感的にわかりやすく, k-tree, 弦グラフ, 極 大クリークサイズ, 部分木による交差表現など は tree-decomposition と深い関わりがある. ま

た branch-width $\triangleright w$ と tree-width$tw$ の間には

$\max\{bw, 2\}\leq tw+1\leq maxt_{z^{bw,2\}}}^{3}$ _という関

係があることが知られている [7].

$hee$_{-decomposition 上で定義される別のパラ}

メータの1つに$tre$.e-length がある. Mee-length

は弦グラフにどれだけ近いかという指標にもな るパラメータであり, tree-length が制限された グラフもよい性質を持つ. 例えば $tr\infty length$が 抑えられたグラフは辺数の少ない spanmer を持 つことが[9] によって証明されている. あるグラ フの

spanner

とは, そのグラフの部分グラフで, かつ 2 頂点間の距離が元のグラフでの距離とさ ほど変わらないものをいう. 多くの分散アルゴ リズムの計算量は spanner の辺数に依存してい るので [4], 辺数の少ない spaxmerを見つけるこ とはこれらのアルゴリズムの計算量を抑えるこ とになる. Tbee-width に対応する branch-width のよう な, tree-length に対応するグラフパラメータは 研究されていなかった. そこで本論文では tree-length に対応する, brani-decomposition 上の パラメータ branch-length について考え, tree-length との関係について考察する. Tree-width はbranch-widthの15倍程度で抑えられるため, tree-length も branch-lengthの定数倍で抑えら

れることは自然に想像できる. では実際にどのく

らいの開きがあるだろうか. 本論文では

branch-width が2以上のとき, tree-length と

branch-lengthが一致することを証明する.

2

準備

グラフ $G$ は連結であるとする. _{$V(G)$ の}

ある部分集合を $V_{X}$ としたとき, $V_{X}$ の直径

$\max_{u,v\in V_{X}}d_{G}(u,v)$ を $diam_{G}(V_{X})$ と表記する.

定義 1. [6] グラフ $G$ _の tfee-doeomposition $\mathcal{T}=(T, \chi)$ とは, 以下を満たす木 $T$ _と $V(G)$ の部分集合の族から成る, $T$ _{の頂点に対応する} 集合(一般に bag と呼ぶがここでは _t-node と呼 ぶことにする) の集合 $\chi$ の2項組とする. 1. $\bigcup_{X\in\chi}X=V(G)$

.

2.

$G$ の任意の辺 _{$\{u,v\}$ に対し}, _{$u$ と $v$ を含む} t-node $X$ が存在する.

3. ある _t-node$X,Y,$$Z$ _{があるとき}, $Y$が $T$_上

のパス $X-Z$ に含まれるなら $X\cap Z\subseteq Y$ を満たす. また tree-decomposition の木 $T$ _の辺を t-edfge と呼ぶことにする. 定義の3つ目の条件は, ”Gの任意の頂点 $v$ に 対し, $T$ _から $v$ を含む t-node を誘導すれば 木であること” と置き換えてもよい. _例えば, 図 1のようなグラフ $G$ があるとき, 図 2 は $G$ _の troe-deoomposition であり, どの頂点 $v\in V(G)$ を含む t-node で誘導しても木であることがわ かる.

$G$_のある tree-decomposition _{$\mathcal{T}=(T, \chi)$ が}

あるとき, 丁の width $\max X_{*}\in\chi|X_{i}|-1$ を

width$(\mathcal{T})$

,

$\mathcal{T}$ の length

$\max_{X:\in\chi}diam_{G}(X_{i})$ を length$(\mathcal{T})$ と表記する. さらに $G$ _の

tree-$\underline{width}tw(G),$ $G$ _の tree-length _{$tl(G)$ とは}$G$ の 図 1: グラフ $G$ 図2: $G$ のある tree-decomposition 全ての tree-decomposition $\mathcal{T}$においてそれぞれ $\min_{T}width(\mathcal{T}),$ $\min_{T}length(\mathcal{T})$ とする. 定義2. [7] $G$ _の branch-decomposition $\mathcal{B}=$ $(T,\mu)$ _とは, 次数 1 または 3 の木 $T$ _と, $G$ _の辺 集合から $T$ の葉集合への全単射$\mu$ の2項組とす る. Branch-decomposition の木 $T$ _{の頂点と辺} をそれぞれ糾node, bedge と呼ぷことにする. グラフ $G$ _のある branch-decompositionを図 3 に示す.

Brani-decomposition $\mathcal{B}=(T, \mu)$ の各卜

$edge\{X, Y\}$ _に対し, mid$(\{X, Y\})$ _{を定義する.}

$T$_の$b\cdot edge\{X, Y\}$ を取り除くことで分けられる

2 つの部分木を$T_{1},T_{2}$ とする. $T_{1}$ に含まれる葉か

ら$\mu^{-1}$で写像される $G$の辺の両端点の集合を $\ovalbox{\tt\small REJECT}$

とする. 同様に乃に含まれる葉から写像される

辺の両端点の集合を $V_{2}$ とする. mid$(\{X, Y\})=$

$V_{1}$ 口 $V_{2}$ と定義する. $B=(T,\mu)$ の蛎 dth を

図3: グラフ $G$ _のある branch-decomposition 図 4: 図 3 の $\tau_{\{x\}},$ $x\in V(G)$ での表現 と表記する. $G$ _の branch-uyidth とは, $G$ の全ての branch-decomposition $\mathcal{B}$ において $\min\epsilon width(\mathcal{B})$ とし, $bw(G)$ と表記する. 定義3. $G$ のある branch-decomposition $(T,\mu)$ とある頂点 $x\in V(G)$ があるとき, $x$ を端点 とする $G$ の辺を

{X,

$y_{1}$

},

$\{x,y_{2}\},$ $\ldots,$$\{x, y_{l}\}$ と

し, b-node $\mu(\{x,y_{1}\}),\mu(\{x, y_{2}\}),$$\ldots$

,

$\mu(\{x, y_{l}\})$

を葉として持つ $T$ の部分木を $\tau_{\{x\}}$ と表記す る. $T$ のある b-node $X$ _に対し, $X$ を含む 部分木 $\tau_{\{x_{1}\}},\tau_{\{x_{2}\}},$$\ldots,\tau_{\{x_{n}\}}$ があるとき, b-node $X$ に対応する頂点集合 $V_{[X]}$ を $V_{[x]}$ $;=$ $\{x_{1}, x_{2}, \ldots, x_{m}\}$ と定義する. 例えば図3の branch-decompositionは $\tau_{\{x\}}$

,

$x\in V(G)$ を用いれば図 4 のように表現できる.

3

Branch-length

Branch-decomposition上の新たなパラメータ branch-lengthを定義し, branch-widthが 2 以上 のときbranch-lengthと tree-lengthが一致する ことを示す. 定義 4. $G$ のある Bmnch-decomposition を

$\mathcal{B}=(T,\mu)$ としたとき, $\mathcal{B}=(T,\mu)$ のlength

を$\max_{\{X,Y\}\in E(T)}diamc(mid(\{X, Y\}))$ と定義

し, length$(B)$ と表記する. $G$ _の bmnch-length

$bl(G)$ _とは, $G$の全てのbmnch-dewmposition $\mathcal{B}$

において$\min e$length$(\mathcal{B})$ とする.

Branch-widthが1のグラフは, width$(\mathcal{B})=$

$1$ を満たす branch-decompo8ition $\mathcal{B}$ が存在す

る. このとき $\mathcal{B}$ の任意の $kedge\{X, Y\}$ にお

いて $|mid(\{X, Y\})|=1$ であり, 直径は $0$ であ るから branch-length は $0$ である. 一方 $tre\triangleright$ decompositionには辺の両端点を含む t-nodeが 存在するのでtree-length は1以上である. 従っ て本論文では, branch-widthが 2 以上の場合を 考える. Branch-length がtrae-lengh と一致すること を証明するために次の2つを示す; 1. $G$ _のbranch-decompositionから length を 増やすことなく $G$_のtree-decompositionが 作れること (補題2), 2. $G$_のtree-decompositionからlengthを増や すことなく $G$ _のbranch-decompositionが 作れること (補題4). 補題 1. $G$ _の branch-decomposition $(T,\mu)$ が あるとき, $T$ のある b-edge

{X,

$Y$

}

_に対し

mid$(\{X, Y\})$ に含まれる $G$ の頂点を $v$ とする と, $v$ は$V_{[X]}$ と $V_{[Y]}$ に含まれる. 図 $5:v\in mid(\{X,Y\})$ 証明. $T$ から _{$kedge\{X, Y\}$} を取り除くことで できる2つの部分木のうち, $X$ _{を含む方の部} 分木を $T_{1},$ $Y$ を含む方の部分木を乃とする. mid$(\{X, Y\})$ が $v$ を含むなら定義より 婿に

含まれ $L_{1}$ $=\mu^{-1}(\{u,v\})$, $\{u, v\}$ _{$\in E(G)$}

を満たす b-node $L_{1}$ と, $T_{2}$ に含まれ $L_{2}$ $=$

$\mu^{-1}(\{v,w\}),$ _{$\{v,w\}\in E(G)$ を満たす糾}node

$L_{2}$ が存在する (図5参照). $\tau_{\{v\}}$ は連結である から, $\tau_{\{v\}}$ は $X$ と $Y$ を含む. よって $v$ は $V_{[X],\square }$ と $V_{[Y]}$ に含まれる 補題2. 任意のグラフ $G$に対し, $bl(G)\leq k$であ るならば$tl(G)\leq k$ を満たす. 証明. $G$ _の branch-length _を $\delta$ とし, length が $\delta$ と等しい _$G$ の branch-decomposition を $(T_{b}, \mu)$ とする. $(T_{b}, \mu)$ から以下のようにしてで きる $(T_{t}, \chi)$ は, $G$_のtree-decomposition_であり lengthは高々 $k$ であることを示す. $T_{t}:=T_{b}$ とする. $T_{t}=T_{b}$ なので $T_{t}$ の頂 点と辺を t-node, t-edge と呼ぶことにする. $T_{t}$ の各 t-node に次のように $V(G)$ _{の部分集合を} 割り当てる. $T_{t}$ の各葉 $L$ には, その葉に写像 される $G$ の辺の端点から成る頂点集合を割り 当てる 言い換えると $T_{b}$ の各葉 $L$ に対し,

$\mu^{-1}(L)=\{u, v\}$ _なる辺 $\{u, v\}\in E(G)$ があ

るとき, $L:=\{u,v\}$ とする. $T_{t}$ の次数3の

t-node $X$ _{に対しては}, $X$ _{に接続する} t-edge _を

{X,

$Y_{1}$

},

{

$X$

,

Y2}, {X,

$Y_{3}$

}

とすると, 図6のよ

うに $X$ _$:=$ (_{$mid(\{X,Y_{1}\})\cap mid(\{X$}

,Y2}))

_俺

pa

_6:

_bnode $X$ $=$ (mid$(\{X,Y_{1}\})\cap$ $mid(\{X,Y_{2}\}))\cup(mid(\{X, Y_{2}\})\cap mid(\{X,Y_{l}\}))$ $\cup(mid(\{X, Y_{3}\})\cap mid(\{X,Y_{1}\}))$

(mid$(\{X,$$Y_{2}\})\cap mid(\{X,Y_{3}\})$)$\cup(mid(\{X,Y_{3}\})$ $\cap mid(\{X, Y_{1}\}))$ とする. 以上のように t-node に割り当てた頂点集合の族を $\chi$ とする. まず$(T_{l}, \chi)$がtree-decompositionであること を証明する. $(T_{b},\mu)$ はbranch-decompoeition で あるから乃は木である. $G$ は孤立点を持たない から, $G$ のどの頂点にもその頂点を端点とする 辺が存在する. Branch-decompoeition の定義よ り $G$ _{のある辺を $\{u,v\}$ とすると $L=\mu(\{u,v\})$} なる t-node$L$が存在する. $(T_{t}, \chi)$ の作り方から $u$ と $v$ は $L$ に含まれる. よって $G$ の任意の頂 点において,それを含む集合が$\chi$に存在し, さら に $G$_{の任意の辺} $\{u,v\}$ において, $u$ と $v$ を含む t-nodeが存在する. $G$ の任意の頂点$x$ において, $x$ を含むかnode で処を誘導した部分グラフは木であることを示 す. $(T_{b}, \mu)$ はbranch-decompositionであるから $T_{b\{x\}}$ は木である. $x$ を含むt-nodeで勾を誘導 した部分グラフと $T_{b\{x\}}$ が一致することを示せ ぱよい. $X$ _を頂点$x$を含むある t-nodeとし,$X$が$T_{b\langle x\}}$ に含まれることを示す. $X$_{が葉であるなら}$X$ _に は$x$を端点とする $G$の辺が写像されているので $T_{b\{x\}}$ は$X$ を含む. $X$が葉でないとき, $X$ に接

続する 3 辺を

{X,

$Y_{1}$

},

{

$X$

,Y2},

{X,

Y3}

とする.

$x\in X$_{であることから}, _{一般性を失うことなく} $x$ は mid$(\{X, Y_{1}\})\cap mid$($\{X$

,

Y2})

に含まれてい

たと仮定できる. このとき $x\in mid(\{X, Y_{1}\})$ と

補題1より, $x$ は$V_{[x]}$ に含まれる. すなわち $X$ は$T_{b\{x\}}$ に含まれる.

mid$(\{X, Y_{2}\}))\cup$($mid(\{X,$$Y_{2}\})\cap mid(\{X$,

Y3}))

$\cup(mid(\{X, Y_{3}\})\cap mid(\{X, Y_{1}\}))$ _{である. 従っ}

てこの t-node $X$ _{に含まれるどの}2_頂点も

mid$(\{X,Y_{1}\}),$ $mid(\{X, Y_{2}\}),$ $mid(\{X, Y_{3}\})$ の

少なくともどれか 1 っに (両方) 含まれる. 仮

定より length$((T_{b},\mu))$ は $k$ 以下であるので

$(1\leq)length(X)\leq k$ を満たす. どの_t-node$X_{i}$

においても $diam_{G}(x_{:})$ は $k$ 以下であるので$T_{t}$ のlength も高々 $k$であることが示せた. _口 $T_{b\{x\}}$ 図 7: $X\in T_{b\{x\}}$ $X’$ _を, $T_{b\{x\}}$ に含まれる勾のt-node とし, $X’$ は $x$ を含むことを示す. $X’$ が葉であるなら 作り方から $X’$ _は$x$ を含む. $X’$ が葉でないと き, $X’$ _{に接続する}3_辺を

{X’,

$Y_{1}$

},

{

$X’$

,

Y2},

{X’,

$Y_{3}$

}

とし, $X’$ を取り除くことで分けら れる 3 つの部分木のうち

{X’,

$Y_{1}$

}

に接続する ものを $T_{1}$, 同様に

{

$X’$

,

Y2},

{X’,

$Y_{3}$

}

に接続す るものを乃,$T_{3}$ とする. 図 7 は _{$T_{b\{x\}}$} を表し ている. $T_{b\{x\}}$ の葉は $x$ が写像されたかnode $\mu(\{x,y_{1}\}),\mu(\{x,y_{2}\}),$ $\ldots,\mu(\{x, y_{l}\})$ から成る.

$X’\in V(T_{b\{x\}})$ より $T_{1},T_{2},T_{3}$ の少なくとも2 つには$x$が写像されている. $T_{1}$ と乃に$x$ が写 像されているとすると, mid$(\{X, Y_{1}\})$ は$x$ を含 み, またmid($\{X$

,Y2})

も$x$ を含む. 従って作り 方から $X’$ _は$x$ を含む. 以上より $x$ を含む t-node で誘導した部 分グラフ簸は木であるので $(T_{b}, \chi)$ は tree-decompositionである.

次に $(T_{t}, \chi)$ がlength$((T_{t}, \chi))\leq k$ を満たす

ことを示す. $T_{t}$ のある葉 $L$ は隣接した2頂点

から成るので $L$ _の length すなわち $diam_{G}(L)$

は 1 である. $T_{t}$ の葉ではない t-node $X$ は

上の表記を用いると, $X=(mid$($\{X$,

Yl})

$\cap$

定義 5. $G$ _の tree-decomposition $(T, \chi)$ があ り, $G$ の各辺 $\{u, v\}$ において, $G$ の頂点 $u$ と $v$ を含む t-node $X$ が1つ定められていると き, $X$ _は辺$\{u,v\}$ に assignmentされていると いう. Tree-decomposition の定義より, $G$の各辺に 対し, 両端点を含む t-nodeが存在するのでその 辺にassignment されている t-nodeを1つ定め ることができる. 定義6. $G$_のtfee-decompolition $(T, \chi)$ が, $G$ _の

各辺 $\{u, v\}$ において

assi9nment

するt-nodeが

定められているとする. 任意の $t$ $ge\{X, Y\}$

に対し, $mid’(\{X,Y\})$ を定義する.

{X,

$Y$

}

を

取り除いてできる $T$ の部分木を $T1,T_{2}$ とする.

$T_{1}$ のt-node に a8s

tgnment

する全ての辺の両端

点の集合を巧とする. 同様に乃のかnode に assignment する全ての辺の両端点の集合を $V_{2}$ とする. $mid’(\{X, Y\}):=V_{1}$ 寡$V_{2}$ とする. 補題3. $G$_のあるtree-decomposition $(T, \chi)$があ り, $G$の各辺においてassignment するt-nodeが 定まっているとする. $T$ _{のある $t- edge\{X, Y\}\in$}

$E(T)$ に対し$mid’(\{X, Y\})$ に含まれる $G$の頂点

を $v$ とすると, $v$ はt-node $X$ と t-node $Y$ に含 まれる.

証明. $T$から t-edge

{X,

$Y$

}

を取り除くことで

できる2つの部分木のうち, $X$ を含む方の部

図8: $T_{X},$ $X$ _の次数が2_でassignment _されて いるとき

$mid’(\{X, Y\})$ に含まれる頂点を $v$ とすると, $v$

は$\tau_{\iota}$ の t-node に assignment するある辺の端

点であり, $T_{2}$ のt-node に assignment する別の

ある辺の端点でもある. $v$ を端点とする辺が

as-signment する $T_{1}$ のある t-node を$X’,$ $T_{2}$ のあ

る t-no$de$_を$Y’$ _{とする. 定義}5_より, $v$ は$X’,Y’$

に含まれる. また, $X$ _と$Y$ は$X^{l}$から_{$Y’$へのパ}

スに含まれる. 従って troe-decomposition の定

義より, t-node $X$ _と t-node$Y$は$v$ を含む. 口

補題4. 任意のグラフ $G$_に対し, _{$tl(G)\leq k$ であ} るならば $bl(G)\leq k$ を満たす. 証明. $\delta$ を $G$ の tree-length とし, length が $\delta$ の _$G$ の tree-decomposition を $(T_{t}, \chi)$ とす

6.

$(T_{t}, \chi)B^{a}\tilde{b}G$ _の branch-decomposition $(T_{b},\mu)$ への変換を与え, 結果得られる $(T_{b}, \mu)$ が length$((T_{b}, \mu))\leq k$ を満たすことを示す. 変換 は次の3 ステップからなる.

1.

$G$の各辺_{$\{u,v\}\in E(G)$ において}, $\chi$の中か

ら $u$ と $v$ を含むt-node を1つassignment

する. 2. 葉は全て $G$ _の辺に assignment _された t-node になるように $T_{t}$ を縮約し, 結果を $(T_{t}’, \chi’)$ とする. 3. $(T_{t}’, \chi’)$の各t-node$X$ _{に対し以下の操作を} 行ったものを $(T_{b}, \mu)$ とする. 図 9: $X$ の次数が4以上でassigment されてい ないとき, $X$ の次数が3以上でassignment され ているとき $G$の各辺$\{u, v\}$において$\mu(\{u, v\})$なる頂点 を用意する. ある t-node $X$ _に assignment する $G$ の辺が _{$l(l\geq 2)$} 本あるとき, それ らの辺を $e_{1},$ $e_{2},$ $\ldots,$$e_{l}$ とする. $X$ の $l-1$ 個のコピーから成るパス $X_{1},$ $\ldots,$$X_{l-1}$ に

t-edge $\{X_{i}, \mu(e_{i})\},$$1\leq i\leq l-1$ と t-edge

$\{X_{l-1}, \mu(e_{l})\}$ を加えた木を$T_{X}$ と呼ぶこと にする (図 8 参照). このとき $X_{1}$_.を, $T_{X}$ の 根とする. $l=1$ のときは$X$ _を$T_{X}$ とする. $X$ _{の次数によって次のような操作を行う.} (a) $X$ の次数が1のとき $(T_{t}’, \chi’)$の作り方から$X$_はassignment されている. $X$_を,$X$をassignment す る辺の木$T_{X}$ と置き換える. このとき $X$ _{と隣接していた} t-node _と$\tau_{x}$ の根 を辺で結ぶ. (b) $X$の次数が2のとき, $X$がassignment されていなければ$X$ を縮約する. す なわち, $X$ に隣接する t-node を $Y$ と $Z$ としたとき, $X$ _を削除し, $Y$ と $Z$間 に辺を加える. $X$_がas8ignment _され ているならば, $Tx$ を加えて

-TX

の根と $X$ _{を辺で結ぶ}. (c) $X$ _{の次数が 3 以上のとき,} $X$ に隣接する t-node を $Y_{0},Y_{Y},\ldots$,Y孤

とする. 図 9 に次数 3 以上のときの変 換を与える. $X$_がassignment _{されていないとき}, $X$ の次数が4以上なら $X$ _を, $X$のコピー から成るパス $X_{1}’,$ $\ldots,$$X_{m-1}’$ に置き換 える. _t-edge $\{X_{i}’, Y_{i}\},$ $1\leq i\leq m-1$

と t-edge

{

$X_{1}’$,

Yo},

$\{X_{m-1}’, Y_{m}\}$ を加

える.

$X$_がassignment _{されているなら}$X$ _を,

$X$ のコピーから成るパス $X_{1}’,\ldots,X_{m}’$

と置き換え, $t- edge\{X_{i}’,Y_{i}\}$)$1\leq i\leq m$ と

{

$X_{1}^{l}$,

Yb}

を加える. さらに$T_{X}$ を加 え, $T_{X}$ の根と $X_{m}’$ を辺で結ぷ. $(T_{b},\mu)$ はbranch-decompositionである. なぜ なら $(T_{b}, \mu)$ のt-nodeは次数1または3であり, $G$の各辺は全単射 $\mu$によって$T_{b}$の葉に写像され ているからである. これ以降は$\mu(e_{i}),$ $\{X_{1}, X_{i}’\}$ 等の頂点,辺も knode, bedge と呼ぶ. $(T_{t}, \chi)$ の tree-lenghは高々 $k$ である. 従っ てlength$((T_{b},\mu))\leq k$であることは, 全てのか

edge

{X,

$Y$

}

$\in E(T_{b})$ に対し mid$(\{X, Y\})$ を含

むtree-decomposition $(T_{t}, \chi)$ の t-nodeが存在

することを示せばよい. $T_{t}’$ の各ひedge と3の操

作で加えられる

&edge

に分けて考える.

ステップ2 で得られる $(T_{t}’, \chi’)$ のあるひ edge

を

{X,

$Y$

}

とする. $mid’(\{X, Y\})$ と, 得られた

brani-decomposition $(T_{b}, \mu)$ の $mid(\{X, Y\})$

は一致するので $mid’(\{X, Y\})$ について証明す ればよい. 補題 2 より, $mid’(\{X, Y\})$ に含まれ る頂点は$(T_{t}, \chi)$ の t-node $X$ に含まれる. また ステップ3の操作で加えられるt-edgeは, $(T_{t}, \chi)$ のある t-nodeを一方または両方の端点としてい る. また $(T_{b}, \mu)$ のある糾 node $X$ において $V_{1^{X]}}$ は, $(T_{t}, \chi)$ の対応する t-node と等しい. 従って 補題1より mid$(\{X, Y\})$ は$V_{[X]}$ に含まれること

から,mid$(\{X, Y\})$ を含む$(T_{t}, \chi)$ にt-nodeが存

在することが示せた.

以上より, $bl(G)\leq k$ である. 口

補題2, 補題 4 より,

定理1. $bw(G)\geq 2$ _{を満たす任意のグラフ} $G$ _に

対し, $tl(G)\leq k\Leftrightarrow bl(G)\leq k$

.

4

まとめ

本論文では, branch-widthが2以上なら tree-length と branch-length が一致することを証明 した. 今後の課題としては, tree-length を branch-decomposition 上で求めるアルゴリズムの設計 が挙げられる. 既存のtree-length を求める近似 アルゴリズムには, 例えば辞書式アルゴリズム LexM [2] や, 距離構造を用いた BFS-Layering [3] 等がある. これらのアルゴリズムはいずれも 3倍近似アルゴリズムである. 他には2倍近似で あると予想されるアルゴリズムDisk-Tree [3] が あるが, それよりよい近似アルゴリズムはまだ 知られていない. 我々はtree-length と branch-lengthが一致することを示したことにより,$tr\infty-$ decomposition と branch-decomposition のよ い性質を互いに利用できるようになった. そこ で branch-decomposition のテクニックや道具な どを用いてtree-length の近似精度を向上させる ことが今後の課題である.

参考文献

[1] Hans L. Bodlaender. A tourist guide

throughtreewidth. Acta Cybemetica,

11:1-21,

1993.

[2] R.Endre Ihrjan Donald Rose andGeorge S.

Lueker. Algorithmic aspects of vertex

elim-ination

on

graphs. SIAMJoumal

on

[3] Yon Dourisbourre and Cyril Gavoille. Tree-Decompositio$ns$ with bags of small

diame-ter. Discrete Mathematics, 2005, To

ap-pear,

extended abstract published in

EU-ROCOMB 03.

Appears also

as

RR-1326-01(2004).

[4] David Peleg and Jeffrey D. Ullman. An optimal synchornizer for the hypercube.

SIAM Journa

on

Computin9, $18:74k747$

,

1989.

[5] Neil Robertson and Paul D. Seymour. Graph minors.I.Excluding

a

forest. $J$

.

Comb. Theory, Series $B:35:39-61$

, 1983.

[6] Neil Robertson and Paul D. Seymour.

Graph minors. II. Algorithmic

as

pects of

tree-width. Joumal

_of

Algonthms,

7:309-322, 1986.

[7] Neil Robertson and Paul D. Seymour.

Graph minors. X. obstructions to

tree-decomposition. J.Combin.Theory Se$\dot{n}es.B$

,

52:153-190, 1991.

[8] Jan ArneRlle andAndrzej Proskurowski.

Algorithms for vertex partitioning

prob-lems

on

partial $k$ -trees. SIAM Joumal

on

Discrete Mathematics, $10(4):529-550$

,

1997.

[9] Cyril Gavoille Yon Dourisboure, Feodor

F. Dragon and Chenyu Yan.

Im-proved spanners for bounded tree-length.