数理解析研究所講究録
第 1799 巻 2012 年 137-144

137

2011 年度冬の LA シンポジウム [27]Approximating Steiner Tree and Tree Cover problems
in Directed Graphs
日比藤戸 敏弘 \dag er

智也 *

概要
任意の Steiner tree $T$ は，根と葉以外にターミナルを含まない極大部分木に一意に分解できるが，$T$ を
それらのいずれもが高さ $L$ 以下であるとき，$L$

制限 Steiner tree という．本稿では，有向グラ

フ上の Steiner tree (DST) 問題に対するグリーデ

ィ近似解法を新たに提案する．同解法は，最小$L$

制限 Steiner tree の:2 ストを $OPT_{L}$ として，コス$L$
トが $O(L\log n)\cdot OPT_{L}$ 以下の DST を出力し，が定数であれば多項式時間であることを示す更に，同解法を用いることで，有向グラフ上の Treecover (DTC) 問題が $O(\log n)$ 倍近似可能であること示す．

の場合，連結頂点被覆問題と等価であり，同闘題は頂点被覆と同等以上に計算困難であることから [8],TREE COVER 問題も NP 困難であるが，2 倍近似可能であることが知られている [16,7].

一般に，無向グラフ上の問題を有向グラフ上で考えると，より難しくなる傾向がある．有向グラフ
上での STEINER TREE 問題は，有向グラフ $G=$$(V, A)$ , 辺コスト関数, 根 $r\in V$ ,:$c$

$Aarrow \mathbb{R}_{+}$が与えられたとき， かterminal の集合
へ至るパスが存在するような最ら発し各 terminal$X\subseteq V$$r$

小コストの有向木 $T$ を求める問題である (本稿では，有向木を各辺が根かち葉の方向へ向かう木として定義する). 有向グラフ上での TREE CO 珂 ER

問題は，有向グラフ $G=(V, A)$ , 辺コスト関数 ;$G$, および根 $r\in V$ が与えられたとき，内の各辺について，その head か tail, もしくは両$C$$Aarrow \mathbb{R}_{+}$INTRODUCTION

1STEINER TREE 問題は，入力として無向グラフ

方を含む有向木の中で最小コストなものを求める問題である．有向グラフ上での STEINER TREE

$G=(V, E)$ , 辺コスト関数 $c:Earrow \mathbb{R}_{+}$ , 根 $r\in V$ ,問題と TREE COVER 問題をそれぞれ DIRECTED

terminal の集合

STEINER TREE (DST) 閤題と DIR の CTED TREE
COVER(DTC) 問題と呼ぶ．この二っの一般化された問題にはともに SET COVER 問題からの簡単な還$P=NP$
元が存在し，
倍近似困難であり，$X\underline{C}V$が与えられたとき，全ての terminal を含む最小コストの木 $T$ を計算する悶

題である．STEINER TREE 問題は SAT に続いてKarp が示した NP 完全問題のーつであり [10], 実
際には倍近似困難であることも知られている [5].
$\frac{96}{96}$

その近似可能性についてはこれまで盛んに研究され続けており，現時点の最良近似は Byrka らによる 139 倍近似アルゴリズムである [2].
TREE COVER 間題は無向グラフ $G=(V,E)$ とコスト関数 $c:Earrow \mathbb{R}+$ が与えられた時， の各$E$辺から端点を少なくとも一つ含む最小コストの木を計算する問題で，Arkin, Halld\’orsson, Hassin に導入された [1]. TREE COVER は辺コストが一定*

豊橋技術科学大学大学院工学研究科情報知能工学専攻\dag er 第 1 薯者に同じ$\Omega(\log n)$でなければ $O(\log n)$ 倍よりも良い近似はできない[6]. 更にこの還元から，根から non-terminal へ向かう辺，および non-terminal から terminal へ向かう
辺しかもたない二部グラフにおいても DST 問題は$\Omega(\log n)$倍近似困難であり，DTC 問題も同様の二部グラフで同じ近似困難性を有することがわかる．

DST 問題に対し，Charikar らは $i\geq 2$ について$O(n^{i}k^{2\dot{z}})$

時間で $i^{2}(i-1)k^{1/i}$ 倍近似アルゴリ

ズムを食欲的なアプローチによって与えた (ただ$k=|X|)$ . これより，任意の定数
し，$\epsilon>0$

につ

138
いて，

$O(|X|^{\epsilon})$倍多項式時間近似が得られ，またとすることで，

SET COVER からの簡単な還元が存在し，二部グ

擬多項式時間ラフでも $\Omega(\log n)$ 倍近似困難であることが分かる

で $O(\log^{3}|X|)$ 倍近似可能であることが示された[6]. この問題に対し，Nguyen は近似アルゴリズムを提示し， を $G$ 内の頂点の最大出次数とした$i=1_{\mathfrak{X}}k$$n^{O(\log|X|)}$[17,3,4]. この結果により，DST 問題に対する多項式時間 polylog 倍近似アルゴリズムの存在が予想され，Konjevod が 2005 年に，Rothvof3 が 2011 年$D^{+}$

とき，その近似保証は $\max\{2, \ln(D^{+})\}$ であると記している [12] しかし，同保証の証明には明らかなに異なるアプローチを試みたが [11,15], いずれも誤りがあり，その主張は成り立たず，一般グラフにCharikar らの近似保証を改善するに至らず，現在
も DST 問題に対する最良の近似保証は $O(|X|^{e})$ でおける DTC 問題の近似可能性は未解決である．本

稿では，DTC 問題を terminaJ 集合と non-terminal

DST 問題の重要性は，この問題が他の多く集合への分割により定まる二部グラフ上の DST 問
題に還元し，前述の近似アルゴリズムを用いることの問題を一般化したものである点である．たとで，DTC 問題が $O(\log n)$ 倍近似可能であることをえば，SET COVER 問題，DTC 問題，GROUPSTEINER TREE 問題などがあげられる．3 つ目のGROUP STEINER TREE 問題について，Halperinと Krauthgamer は木状のグラフに対する GROUP
倍STEINER TREE 問題に対してさえ近似困難であり，それによって GROUP STEINERTREE 問題の一般化である DST 問題もまた同等の

示す．

ある．

$\Omega(\log^{2-e}n)$近似困難性を持つことを示した [9].
入カグラフに制限を加えた DST 問題に関しては，Carikar らのアルゴリズムによって入カグラフの最長パスが定数 $L$ に制限されたグラフにおいて倍近似を得ることができる [4]. また Zoeinと Khuller は，teminal を除いた頂点集合$O(\log n)$$V\backslash X$

が深さ $L$ の木であるグラフの場合に対し，$(L+1)$ .
$O(\log n)$倍近似アルゴリズムを示した [18].

$L$ 制限
本論文では，
Steiner tree という限定された DST を考え，最小 $L$ 制限 Steiner troe コストの2. $(L-1)\cdot H(|X|)$ 倍以下のコストを持つ DST を出力し，任意の定数 $L$ で多項式時間な近似アルゴリズ

ムを示す．ただし，

DIREcTED STEINER TREE

2

DST 問題では，有向グラフ $G=(V, A)$ , 辺コスト関数 $c:Aarrow\sim$ , 根 $r\in V$ , および teminal の集合を入力とし， から各 terminaJ へ至る
パスを含む有向木 (有向 Steiner tree, DST) の中$X\subseteq V$$r$で，最小コストのものを求める問題である．
$L$ 制限本節では DST 問題に対し，Steiner treeという制限され DST の中で最小なもののコストの2. $(L-1)\cdot H(|X|)$ 倍以下のコストを持つ DST を出力する，そして が定数であれば多項式時間で$L$ある近似アルゴリズムを示す．またこの結果から，
が定数 を超える長さのパスを誘導しない
グラフにおいては，DST 問題が 2 $\cdot(L+1)\cdot H(|X|)$$L$$V\backslash X$

倍できることを示す．これは，入力に制限を加えた
DST 問題についてこれまでに知られている結果をすべて含むものである．

$H(k)= \frac{1}{1}+\frac{1}{2}+\cdots\frac{1}{k}\leq 1+\ln k$である．また，この結果から
ラフの最長パスが定数$L$$V\backslash X$

が誘導するグに制限された入カグラフ

における DST 問題に対し，2 $\cdot(L+1)\cdot H(|X|)$ 倍

近似アルゴリズムを与える．

Greedy algorithm

任意の DST を観察すると，それ (の辺集合) を
根と葉のみが teminal である部分木に一意に分解

DTC 問題は DST 問題の特別な場合である．有向グラフ
における DTC とは， 内の各辺からその head か tal もしくは両方を含む有向木である．
$G$

2.1

$G$

できることが分かる．根と葉のみが terminal である木は亀 11 Steiner tree と呼ばれ，次のように定義される．

DTC 問題の目的は，非負辺コスト付き有向グラフが与えられた時，最小コストの DTC を計算す

定義 1. full Steiner

ることである．前述の通り，DTC 問題についても

ある．

$G$

$R\mathfrak{r}eT$は次のような有向木で

139
1.

$T$

の根 $r(T)$ は $x_{U}\{r\}$ に含まれる．

2.

$T$

の葉はすべて $X$ に含まれる．

辺のない terminal のみで構成される部分グラフ$(XU\{r\}, \emptyset)$$\{r\}$

3. そのほかの$T$

部分グラフ $T$ の頂点集含と辺集合をそれぞれと表す． のコスト，つまり 内の辺のコストの合計を $c(T)$ で表す． が有向木のとき，
$T$

$r$

からすべての terminal へのパスが存在するので DST が存在し，深さ優先探索の頂点は $X$ に含まれない．

$V(T),$ $A(T)$は明らかに PSol である．同様に $R_{F}=$である PSol にはなどでコストが $c(A_{F})$ 以下の DST を構築できる．

さらにアルゴリズムで使用する操作を 2 つ定義

$T$

する．

$T$

$r(T)$$X(T)$ ははその根を表し，$T$が含む $r(T)$ 以

外の terminal の集合とする $(X(T)=X\cap(V(T)\backslash$$\{r(T)\}))$.

定義 2. 木 $T$ のコスト密度 $d(T)$ は木 $T$ の中の ter-minal 一つあたりにかかるコストであり，$d(T)=$$c(T)/|X(T)|$ と定義する．

ある 2 っの有向木$T$ 内のすべての辺コ
定義 4. 木 $T$ を縮約するとは，にし， に含まれる $r(T)$ 以外の terminal
を terminat 集合から取り除く操作である (すなわ$c(e)\sim O\forall e\in A(T^{*}),$ $X\sim X\backslash X(T))$ .
ち，
ストを

$T$

$0$

定義 5. metric closuoe はすべての頂点対に対して，コストがその頂点間の最短パスと等しい辺をグラフ上に仮定する操作である．

を仮定する．ここでさらに処のある頂点 $v_{1}\in V(T_{1})$ を根とする，r(乃)へのパスを含むような有向木が追加されたとする．

す．Charikar らのアルゴリズムでは，根を入力ですると $r(T_{1})$ から $r(T_{2})$ へのパスができることによ

与えられたと亀に含まれるすべての頂点へり，のパスができる．つまり，新たに有向木を追加する
ことによって処と乃は $r(T_{1})$ を根とする一つの定の有向木を再帰的に計算し，全ターミナルを含むまで繰り返し追加していくことで，Steiner tree を$r(T_{1})$から$T_{1},$$T_{2}$$T_{1}$

木にまとめられたと考えることができる．

集合にさらに有向木を加えていくことでーっの有向木にまとめる Greedy アルゴリズムを考えることができる．

次の性質をもった $G$ の部分グラフ Partial Solution を定義する．
定義 3. 次の性質を満たすグラフ $G$ の部分グラフ

Parlial Solution と呼ぴ，PSol と

1. $F$ 内で $\delta^{-}(v)=0$ である頂点

非空で，$r\in R_{F}\subseteq X$ 俺 $\{r\}$$F$

構築している．これに対し，我々のアルゴリズムでは，その時点で から到達不可な任意のターミナルを根とする高さ一定有向木の中から，コスト密度がよいものを計算し追加することを繰り返す．

Algorithm 1. Greedy algorithm

1. $Farrow(X\cup\{r\}, \emptyset)$2.

$X_{(},$$\wedge X$

3. $i\sim O$

内で，各頂点は$R_{F}$$v$の集合$R_{F}$$X_{i}=\emptyset$(a) metric closure を計算

は(b) $X\cup\{r\}$ 内の頂点を根とする木でコストである．

密度が最小な有向木 $r*$ を計算のいずれかの頂点から(c) $Farrow F\cup T^{*}$

到達可能である．

3.

こ固定して，コスト密度のよい高さ一4. repeat until

表す．

2.

$r\ovalbox{\tt\small REJECT}$$r$

このことから，最初はバラバラであった有向木の$F=(V_{F},A_{F})$ を

DST 問題に対するグリーディアルゴリズムを示(d)$V_{F}\supseteq X\cup\{r\}$$T^{*}$$c(e)$
を縮約．

$\sim$$X_{i+1}\sim X_{i}\backslash X(T^{*})$

$F$

内で

$x_{k}\in R_{l^{\gamma}}$から到達可能な頂点の集合を琉(e) $i\sim i+1$

と表す．

5.

$F$

から DST を再構築

$0\forall e$$\in$$A(T^{*})$,

140
補題 1. Algorithm 1 の各繰り返しの始めで $F$ はできるので$R_{F}=X_{i}\cup\{r\}$ である．
PSol であり，をカバーする繰り返しのときのProof. アルゴリズム開始時の$F$

は $(X\cup\{r\}, \emptyset)$ で$\sum_{\dot{\iota}=1}^{|X|}d(i)$と表すことができる．ある :$X$は少なくとも$|X_{i}|$$|X|-i+1$ であるので，あり，明らかに $R_{F}=X\cup\{r\}$ である PSol である．
$i$$\sum_{*=1}^{|X|}d(T_{i})\leq\sum_{1=1}^{|X|}\alpha\cdot|X|-i+1$

番目の繰り返しで $F$ は $R_{F}=X_{1}\cup\{r\}$ である PSol であるとする．番臼の繰り返しで $x_{k}\in$$i$$X\cup\{r\}$を根とする有向木$\tau_{:}*$

が $F$ に加えられたと$= \alpha\sum_{i=1}^{|X|}\frac{1}{|X|-i+1}$

する． が加えられたことによって， からの各 terminaJ へのパスでき，さらに $X(T^{*})$ からの$\tau_{i}*$$x_{k}$

パスが存在した頂点集合にもる．よってPSol となる．

$T_{*}^{*}\cup F$$x_{k}$$X(T_{:}^{*})$

からのパスができは $R_{F}=\{r\}\cup(X_{1}\backslash X(T^{*}))$ である$X_{i}\backslash X(T^{*})$$=\alpha\cdot H(|X|)$

は $X_{i+1}$ であるので，$i+1$番目の繰り返しにおいても $F$ は $R_{F}=X_{i+1}\cup\{r\}$よって，コスト密度が$\alpha/|X|$である$\tau*$を見つけることができれば，Algorithml はコストが$H(|X|)$ である$\alpha$.

DST を出力する．口であるような PSol である．

よって補題は成り立っ
補題 2. 有向木$\tau*$

口を多項式時間で見つけることができるならば，$Algoi\dot{\tau}thm1$は多項式時間で正しくProof. アルゴリズムの各繰り返しで明らかに
サイズは一つ以上小さくなる．また$\tau*$

$X$

の

を多項式

時間で見つけることができるならば，アルゴリズ
ムの各ステップは多項式時間で動作する．よって，Algorithm 1 は多項式時間で動作する．

繰り返しが終了したとき，$X_{i}=\emptyset$

補題 1 より，繰り返しを抜けたあと$\tau*$を見つけることは$F$

は $R_{F}=\{r\}$が $c(A_{F})$ 以下の DST を容易に作ることができる．

よって Algorithm 1 は正しく動作する．口補題 3. コスト密度が$\alpha/|X_{i}|$以下の$\tau*$

を各繰り

返しで見つけることができれば，Algorithm 1 が出
力する $DST$ のコストは $\alpha\cdot H(|X|)$ 以下である．
$X_{1},x_{2},$ $\ldots,$ $x_{|X|}$える．

定義 6. l-level 木とは根から葉までにはアルゴリズムによって収縮されていった順にソートされた terminal とする．あ$X(T^{*})$ が terがる有向木に加えられた時，
minal 集合から取り除かれる．これはコスト
で $X(T^{*})$ を解に加えたと考えることができ，各 termmal に $d(T^{*})$ のコストを支払うことで，その terminal を解に加えたと考えることができる．した$F$$c(T^{*})$

がって，アルゴリズム全体のコストはそれぞれのterminal に支払ったコストの総和と考えることが

$l$

より多くの

辺が存在しない有向木である．
定義 7. 構成要素の掴 lSteiner tree がすべて l-level木である $DST$ を$l$である．よってである PSol である．そのような PSol からはコスト$\tau*$

実際にコスト密度が良い木

難しい．そこである制限を加えた DST について考動作する．

Proof.

density

2.2 Finding
minimum
Steiner tree

グラフ $G$ 内の

$r$

制限

$St\dot{\alpha}ner$toee と呼ぶ．

を根とする最小コスト $L$ 制限とする．また，full Steiner
tree の中で最もコ- スト密度の良い Llevel 木をSteiner tree を$T_{OP_{L}}$$T_{L}^{*}$とする．本節では，Charikar らのアルゴリズムによってコスト密度が $d(T^{*})\leq(L-1)\cdot d(T_{L}^{*})$ である$\tau*$を見つけることができることを示し，さらに窺のコスト密度を保証することで、コスト密度が$d(T^{*})\leq 2\cdot(L-1)\cdot c(T_{OPT\iota})/|x_{:}|$の木を多項式

時間で見つけることができることを示す．

teminal 集合 $X$ から$k$

個の頂点を含む$r$を根とする有向木で，コスト密度最小の i-level 木のコス

ト密度を $d_{OPT}^{(i)}(k,r,X)$ と表す Charikar らは [4]で次の補題を示した．
補題 4. Chankar らのアルゴリズムで，指定さ$d(T_{BBST})\leq(i-1)$ .
を根とする，$d_{OPT}^{(:)}(k,r,X)$ であるような-level 木 TBEST を

れた頂点

$f$

$i$

$O(n^{i}k^{2i})$

時間で見つけることができる．

141
あらゆる

と $r’\epsilon X\cup\{r\}$ にっいて Charikar$k$

この Algorithm 2 で得られた $\tau*$ のコスト密度がらのアルゴリズムを実行することで，次の系が導

2.

ける．

ることを証明する．

$d(T^{*})\leq(L-1)\cdot d(T_{L}^{*})$
系 1. 定数 $L\geq 2$ に対して，であるような L-level 木を見つける多項式時間
近似アルゴリズムが存在する．
$\tau*$

Algorithm 1 の各繰り返しで常にを見つけるをことが出来たとしても，Algorithml は出力するとは限らない．よって，Algorithml の各であるような 1 ひ level 木 $T$ ‘であ$c(T_{OPT_{L}})/|\overline{X}|$

補題 5. Algorithm 2 の木において， 内にへのパスが存在するならば， の$v_{i}\in V_{i}$からからの間の頂点で$x_{i}$$x_{i}$$T$$T\in \mathcal{T}$

$T$

$T$

$v_{i}$

が分岐することはない (出次数が 1 より大きいものはない).

$T_{L}^{*}$$T_{OPT_{L}}$

繰り返しにおける町のコスト密度に対する保証を与える必要がある．
$T_{OPT_{L}}$が与えられたとす$Rp=\{r\}\cup\tilde{X}$る．補題 1 より は PSol であり，とする．このとき，TOP 翫からコスト密度が 2 .
$F$であるような klevel 木$\tau*$

けることができることを示す．明らかに$d(T^{*})$

$F$

を見つ

$d(T_{L}^{*})\leq$である．

ムでコスト密度の小さい$\tau*$

を得ることができる．

Algorithm 2.
制限 Steiner tree の最適解を選ぶ
Toae 覧から$L$$\tau*$$X_{i}$$v_{i}$から$Tarrow\emptyset$$x_{j}\in\tilde{X}$$v_{i}\in V_{i}$補題 6. Algorithm 2 によって求まる

Proof. Step 4 で選ばれたある
このときの$\tau*$$i\neq j$である最初の $vj\in V_{j}$ にぶつかるまで $T_{OPT_{L}}$ を逆向きにたどる．それにより$\mathcal{T}$に追加する．これをすべての$L$について考える，は有向木である．

$\tau*$の葉の頂点までのパス
以下であることを示すことによって， が

さらに $r(T^{*})$ からある
長が$\tau*$$\tau*$$\tau*$&level 木であることを証明する．
Algorithm 2 より， の葉は terminal である．
$\tau*$から葉である$x_{i}$

からまで$x_{i}$$\tau*$

上のパスを考える．

へのパス上には$V_{i}\cup(V\backslash$はである頂点しか存在しない．またから距離 以制限 Steiner tree であるので，$x’\in内に頂点が存在する． X$ であるこ$L$

$T_{W_{L}}$$V_{F})$$L$$r(T^{*})$$x’\in X\backslash \tilde{X}$$x’\in V_{i}$ である．よっとから $x’\in V_{F}$ であるので，

terminal に対して行う．

上での $x’$ からへのパスに含て，補題 5 よりまれる頂点で分岐はない． から距離 $L$ 以内に$x’$ からへのパスは Step 5 で一本の辺が存在し，は &levelに変換されることから，Step5 でのTree である．Step 6 では木の高さが変わらないた$\tau*$

3.

は L-level$-$
は $T_{OPT_{L}}$ の部分グラフであり，

Step 2 より，から，$\tau*$木である．

$r(T^{*})$

求めたパスをへのパスの聞で $T$ が分岐し

$x_{i}$からたとする．すると，Step2 である頂点を超晦から賜へのパスの間の頂点を通り，えて $r(T)$ までを辿ったパスが存在するこ
Step2の操作に矛盾する．口とになる．これは$r(T^{*})$

2.

のつの連結成分であるのでと $T_{OPT_{L}}$ が与えられたとき，次のアルゴリズ

1. 集合族

$T$$T_{\psi_{L}}$ある繰り返しでの $F$ &$c(T_{OPT_{L}})/|\tilde{X}|$Proof.

内のパスで同じ頂点から始まるバスは一つの有向木にまとめる．

$T$$x_{i}$$X’$$r$$x_{i}$

4.

に含まれる有向木で最もコスト密度が良い
有向木を一つ選ぶ．
$T$$\tau*$

5.

6.

$\tau*$にある $\delta^{+}(v)=\delta^{-}(v)=1$ である頂点を$\tau*$

め，補題は成り立っ口

metric closure の辺を使って一本の辺に置き換補題 7. 最小 $L$ 制限 Steiner tree $T_{OPT_{L}}$ から計算

える．

した

$\tau*$の根を$v_{j}\in$

巧から約よって 2 ストが$0$$r(V_{j})$に置き換える (縮である辺 $(r(V_{j}), v_{j})$ が存$\tau*$のコスト密度は 2$\cdot c(T_{OPT_{L}})/|\tilde{X}|$

以下で

ある．

Proof. Algorithm 2 で作られた集合族

$T$

全体のコ

在するため，metric closure の辺を用いてコススト密度が高々ト密度と level が変わらない有向木を作ることし，その中で最もコスト密度の良い部分集合を選択するという手順から補題を証明する．

ができる).

$(2 \cdot c(T_{OPT}))/|\tilde{X}|$であることを示

142
Algorithm 2 によってすべての terminal が 内の木にカバーされるので は個の teminal を
$T$

$T$

したがって，系 1 より$|\overline{X}|$$d(T_{BEST}) \leq 2\cdot(L-1)\cdot\frac{c(T_{OPT_{L}})}{|X_{*}\cdot|}$

カバーする．

Step 5, 6 の操作ではコスト密度は良くなったとしても悪くなることはないので，Step4 での を考える．Algorithm 2 の手順より，木 $T\in T$ の辺には Toに含まれる辺しか含まれない．よって，$\mathcal{T}$$P’\Gamma_{L}$

ある共通の頂点を含む木

かないことを示すことによって

2$T_{OFT_{L}}$$T\in \mathcal{T}$二つの木が高々 2 つまでし

$T\in \mathcal{T}$$\mathcal{T}$

全体のコストがよって補題は成り立っ．口

2.3 Approximating
STEINER TREE

補題 3, 8 より、ただちに次の定理 1 が成り立つ．

以下であることを示す．
は $T_{OPT_{L}}$ の部分木である．よって，ある$T_{1},T_{2}\in \mathcal{T}$$r(T_{1})\in V(T_{2})$が共通の頂点をもつならば，または $r(T_{2})\in V(T_{1})$ である．そうでないならば，$r(T_{1})\not\in V(T_{2})$DIRECTED

かつ $r(T_{2})\not\in V(T_{1})$定理 1. Algorithm 1 は，コストが $2\cdot(L-1)\cdot H(|X|)$ .
$c(T_{OP’\Gamma_{L}})$$L$ が定数であれ以下の $DST$ を出力し，ば多項式時間で動作する．
制限 Steiner tree に対する近似比は Zekovsky

で処と乃が共通の頂点を持つことになり， からの辺と乃からの辺の二つが入る入次数が 2 の頂も与えており，その近似比は $(2+\ln k)^{L-1}$ である

点が $T_{OPT_{L}}$ に存在することになるため，$T_{OPT_{L}}$ がが [17], 定理 1 はこれを改善するものである．

$L$$T_{1}$の根木であることに矛盾する．よって，各となる頂点が高々2 つの木にしか含まれないことを示せば，補題は成り立つ．

一般の DST 問題に対する Algorithml の近似比

$T\in \mathcal{T}$ある木$r(T)\in$の根 $r(T)$ を考える．Step 2 より，$T\in \mathcal{T}$

巧と仮定できる．Step 2 で$x_{i}$

以外の $Xj$ かは，Charikar らの解析と同じ手法を適用でき，2 .
$i^{2}(i-1)\cdot|X|^{1/i}$く$O(k^{\epsilon})$となる．これは Charikar らと- 同じ倍近似であり，polylog 倍近似は得られていない．

ら辿ったパスが $r(T)$ まで来たとするならば，必ずDST 問題に対する近似アルゴリズムは，一般ので止まる．よって頂点 $r(T)$ を超えて辿ること場合だけではなく，入カグラフを制限した場合も$r(T)$ができるパスは$x_{i}$

からのパスのみだったはずである．

$r(T)$ で止まったパスは

Step 3 によって $T$ にま研究されている．

$V\backslash X$

が辺を誘導しないグラフ

は quasi-bipartite グラフと呼ばれるが，無向グラフ

をにおける ST 班 NER TREE 問題では，入力を quasi-

カバーした木の高々2 つしかない存在しない．よっbipartite グラフに制限することで，一般グラフ上よりも良い近似保証の得られることが繰り返し観察されている [13, 14, 2]. 例えば Robins と Zelikovskyの結果では，一般グラフでは約 155 倍近似であったのに対し，quasi-bipartite グラフに制限すると
約 128 倍近似が得られている [14]. 有向グラフに$r(T)$ を含むような木はとめられるため，$T$と$x_{i}$て，どの頂点も高々 2 つの木のみにしか含まれず，$\mathcal{T}$のコストの合計は 2 $\cdot c(T_{OPT_{L}})$ を超えない．
$T$
したがって，2$c(T_{OPT_{L}})/|\tilde{X}|$

全体のコス ト密度はである． の中で最もコス$\mathcal{T}$ト効果の高い部分集合が選択されることから，

Algorithm 2 で選ばれる部分集合のコスト密度は2を超えない．口$c(T_{OPT_{L}})/|\overline{X}|$補$\mathfrak{B}8.$

Charikar らのアルゴリズムによって，コスト密度が 2 $\cdot(L-1)\cdot c(T_{OPT_{L}})/|X_{l}|$ 以下の L-level

有向木 $T_{BEST}$ を見つけることができる．

Proof. 補題 6, 7 より，明らかに$d(T_{L}^{*}) \leq\frac{2\cdot c(T_{OPT_{L}})}{|X_{i}|}$

おいては，SET COVER 問題からの簡単な還元より，quasi-bipartite グラフにおいても DST 問題は$tl(\log n)$倍近似困難であることが分かる．しかし，quasi-bipartite グラフにおける任意の DST は 2 制
限 Stemer tree である．よって，次の系が導かれる．
系 2. $quasi-bipa\hslash ite$ グラフにおける $DST$ 問題は，

2. $H(|X|)$ 倍近似可能である．

つまり，一般グラフにおける$\Omega(\log^{2-\epsilon}n)$倍近似

困難性 [9] と併せることで，有向グラフにおいては，

143
一般グラフと quasi-bipartite グラフとで近似可能

補題 10. $DTC$ 間題のインスタンス $(G,r, c)$ から作性に差が生じることが示された．より一般には，次成した $DST$ 問題のインスタンス $(G’, r’, X,c’)$ につの系が成り立っ．

$G’$ における任意の $DST$
いて，
TDST から $G$ における同コストの $DTC$ TDTC を多項式時間計算でき

系 3.

$V\backslash X$

が誘導するパスの長さが定数 $L$ 以下であるグラフにおいて，$IlST$ 問題は $2\cdot(L+1)\cdot II(|X|)$倍近似可能である、

この系は，グラフ全体，あるいは$V\backslash X$の深さがある定数で抑えられた場合について，これまでに得られている既知結果を包含する．

$G$ の任意の $DTC$ に対し同コストの $DST$
る．また，

が

に存在する．

$G^{l}$

Proof.
$G$

上の $r’$ を根とする木 $T’$ が与えられた時，$G’$

上の $T$ は$T^{J}$

が辺 $(u,x_{(u,v)})$ と $(x_{(,\iota,v)}, v)$ の両方を含んでいたときかっその時に限り，辺 $(u,v)$ を含むとする．このような $T$ は明らかに $T’$ と同じコストを持つ

3

DIRECTED TREE COVER$r$を根とする木であり，これは明らかに多項式時間で計算できる．
$T’$

DTC 問題は，有向グラフ $G=(V, A)$ , 辺コスト関数 $c:A\sim \mathbb{R}+$ , および根 $r\in V$ が与えられたとき， 内の各辺について，その head か tail もしく
は両方を含み を根とする有向木でコスト最小なものを求める問題である．本節では DTC 問題から二部グラフ上の DST 問題への近似率保存帰着を示が DST 問題の実行可能解 $T_{DS’T}$ であったとする．その $T’$ に対する $T$ を考える．TDST がすべての $x_{(u,v)}\in X$

$G$

$r$

すことで，DTC 問題に対する $O(\log n)$ 倍近似アルゴリズムを示す．

DTC 問題の入力として，辺コスト付きの $G=$$(V, A)$ と根 $r\in V$ が与えられたとする．DTC 問
題のインスタンス $(G, r, c)$ から DST 問題のインス
タンス $(G’,r’,X,c’)$ を作る．まず，$G$ の各辺 $(u,v)$$G’$ のに対して terninal $x_{(u,v)}\in X$ を追加する．

頂点集合は $V’=V$ 火 $X$ である．追加した頂点は
金て terminal であり，もとあった頂点は全て non-terminal とする．根 は と同じ頂点とする．そして，辺 $(\%, v)$ を削除し，代わりに同じコストの
$r’$

$r$

辺 $(x_{(u,v)},v)$ を追加する．さらにコストが$(u,x_{(u,v)})$

$0$

の辺

と $(v,x_{(u,v)})$ を追加する．これらの辺の集合が $G’$ の辺集合 $A’$ となる．
$|X|=|A|,$ $|A’|=3|A|$であり，明らかに多項式時間で構成可能である．

を含むことから， は$T’$

くとも一方を含む． が含んでいた
$T’$

$u$

と

$u$

と

$v$

$v$

の少な
は $T$ に

$T$ は変換したときにもそのまま保持されるため，
TDST と同じ 2 ストである DTC 問題の実行可能解となる．
よって DTC 問題のインスタンス $(G, r, c)$ から作成した DST 問題のインスタンス $(G’,r’,X, c’)$ について， における任意の DST TDST から同じコス$G^{l}$

トの$G$における DTC TDTC を多項式時間で計算

できる．
$G$

の木

上の
$T’$

$r$

は

$G’$ 上を根とする木 $T$ が与えられた時，$T$が辺 $(u, v)$ を含んでいるときかつその時に限り，辺 $(u,x_{(u,v)}),$ $(x_{(u,v)},v)$ を含むとする．
このような $T’$ は明らかに $T$ と岡じコストを持つ $r’$を根とする木である．
$T$

が DTC 問題の実行可能解

する．その

$T$

に対する

$T’$

TDTC であったとを考える．TDTC の頂点集合が vertex cover であることから $T’$ はすべての$x_{(u,v)}\in X$

に対して， と$u$$v$の少なくともどちら$T’$ にコストがか一方を含む．よって，

$0$

である辺

か $(v,x_{(u,v)})$ を適切に加えることで DST$(X, V’\backslash X)$ を頂点集合の分割とす
補題 9. $G’$ は，$(u,x_{(u,v)})$

る 2 部グラフである．

問題の実行可能解 TDST を作ることができる．

Proof.
$X$$G$の各辺 $(u,v)$ について，teminal $x_{(u,v)}\in$を挿入するとともに，辺 $(u,v)$ の代わりに，

$u,$

$v$

ともに追加した terminal とっながる辺が加えられ，$G’$ で $V$
はそのような辺しか含まない．っまり，に倉まれる頂点と隣接する頂点は terminal のみであり，terminaJ 同士が隣接することもない．口$A’$

したがって DTC 問題のインスタンス $(G,r,c)$ から作成した DST 問題のインスタンス $(G^{J}, r’,X,c’)$には任意の DTC TDTC の:2 ストと同じコストの $G’$
における DST TDST が存在する．口定理 2。 $DTC$ 闘題は 2 $\cdot H(|A|)$ 倍近似可能である．

144
Proof. 補題 10 より，DTC 問題を DST 問題に近似率保存帰着することができる．還元したグラフは補題 9 より，terminal である頂点と terminal でない
頂点で分かれる 2 部グラフである．このグラフは明らかに quasi-bipartite グラフである．よって系 2
より DTC 問題を 2 $\cdot H(|X|)$ 倍近似で解く事ができ
口る[2] J. Byrka, F. Grandoni, T. RothvoB, and
L. Sanit\‘a. An improved LP-based approximation for Steiner tree. In Proceedings of the $42nd$$ACM$ Symposium on Theory of Computing, pp.
583-592, 2010.
[3] G. Calinescu and A. Zelikovsky. The polymatroid
Steiner problms. J. Comb. Optim., $9(3):281-$, 2005.

[4] M. Charikar, C. Chekuri, T. Cheung, Z. Dai,
A. Goel, S. Guha, and M. Li. Appraximation
algorithms for directed Stemer problems. J. Algorithms, 33(1) $:73-91$ , 1999.
[5] $hI$ . Chleh\’ik and J. Chleb\’ikov\’a. The Steiner
tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406:207214, 2008.
$8UetFCe\circ ivgeer$

1998.

. $AJtohurmaedho!theACM,$[7] T. Fujito.

$45?_{4):634-652}^{rox\dot{m}ating}$

How to trim an mst:

A 2-

$C\circ ver.InS3rdIaPP^{r\dot{m}mationa}\varphi_{ALP,Vo1.4051ofLNCS,pp}^{rithmform\dot{m}\dot{m}umcoettree}$$431\triangleleft 42$[14] G. Robins and A. Zelikovsky. Tighter bounds
for graph Steiner tree approximation. SIAM .
$Dis$ cret. Math., 19:122-134, 2005.
$J$[15] T. RothvoB. Directed steiner tree and the lasserre
hierarchy. Arxiv preprint $arXiv:l111.5473$, 2011.

$235$[1] E. Arkin, M. Halld\’orsson, and R. Hassin. Approximating the tree and tour covers of a graph.
Inform. Process. Lett., 47:275-282, 1993.

[6]$D\dot{\tau}s$1999.

[16] C. Savage. Depth-first search and the vertex
cover problem. Inform. Process. Lett., $14(5):233-$

参考文献

$294$

[13] S. Rajagopalan and V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree
problem. In Proc. 10th Annual ACM-SIAM
crete Algorithms, pp. 742-751,
Symposium on, 2006.

[8] M. Garey and D. Johnson. The rectilinear
Steiner-tree problm is NP-complete. SIAM
Joumal on Applied Mathematics, 32:826-834,

1977.

[9] E. Halpein and R. Krauthgamer. Polylogarithmic inapprnimabllity. In Proceedings of the $S5th$
annual $ACM$ Symposium on Theory of Computing, pp. 585-594, 2003.
[10] R. Karp. Reducibihty among combinatorial problems. In Complexity of Computer Comput $tim$,
pp. 85-103. Plenum Press, New York, 1972.
[11] G. Konjevod. Directed Steiner trees, lmear pro
grams and randomized roundin . Manuscript, 8$\cdot$pages, 2005.

$g$Approximating the minimum directed tree cover. In Intemational Conference
on $Combinato\dot{m}l$ optimization and Applications,pp. 144-159, 2010.

[12] V. Nguyen.

, 1982.

[17] A. Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree prob
lem. Algorithmica, 18:99-110, 1997.

[18] L. Zosin and S. Khuller. On directed Steiner. In Proceedings of the lSth annual ACMSIAM Symposium on Discrete Algorilhms, pp.
$5k63$ , 2002.
$tr\infty$