数理解析研究所講究録
第 833 巻 1993 年 98-10998

グラフの多重目標点分離問題に対する
近似アルゴリズムについて
京都大学数理工学科

1

前田

尚久

(Naohisa Maeda)

永持仁(Hitosi Nagamochi)

茨木俊秀(Tosihide Ibaragi)$k=3$ かっグラフが平面のときはさらに高速な序論

アルゴリズムが設計されている[4] . H. Saran とこのネッ トワーク

V. V. Vazirani は最適解の $2(1-1/k)$ 倍以内の重みを指定された要求を満たすいくっかの成分に分けを持つ分割を O(n. M(n, m)) 時間で構成するアルる重み最小の分割を見っける問題について考える.

ゴリズムが提案している ([7]). ただし, $M(n, m)$

ネッ トワーク $(G, w)$ を考え,

このような問題の中で,ネッ トワーク( $G=$$(V, E))w)$ と分割数 $k\geq 2$ が与えられた時,
$k$

$G$

個の成分に分割する辺の部分集合を考える.

のような辺の部分集合のうちで,

は

$n$

節点,

$m$

辺のネッ トワーク上で最大流問題

をを 1 つ解くための時間である. 多重カット問題は,
こ一般のグラフにおいて $k=3$ とした場合,

その辺の重みのいは平面グラフに限っても

$k$

ある

をその問題のサイズ

和が最小であるものを求める問題は多重分離問題の一っとした場合には NP- 困難であることが示さ(Multiway Split Problem) と呼ばれる. これに対

れている

し,

が目標点と呼ばれる$k$

これらの点を一っずつ含む

$k$

$G$

個の点を持ち,$G$をの個の成分に分割する

辺の部分集合を考える. そのような辺集合のうち[1].

多重カッ ト問題に対しても最適解$2(1-1/k)$ 倍以内の重みを持つ分割を $O(k\cdot$$M(n, m))$ 時間で構成するアルゴリズムが提案さ
れている

[1].

重みの和が最小のものを求める問題は多重カット本研究では, ネッ トワーク $(G=(V, E),$ $w$ ), 目
問題 (Multiway Cuts Problem) と呼ばれる.

このうち多重分離問題はっと考えると,るを問題のサイズの一NP- 困難になることが知られてい$*\cdot/$

トワークを少なくとも 1 個の目標点を持つ

個の

$k$

成分に分ける分割を求める多重目標分離問題を新[3] が, 最適解を得るための $O(n^{k^{2}/2-k+11/2})$ 時たに導入する. この問題は $T=V$ であれば多重間 (これは,る)$k$

標点 $T\subseteq V$ , 分割数 $k\leq|T|$ が与えられた時,$k$を定数とみなせば多項式時間であのアルゴリズムが得られている

[3].

また,

カット問題, $k=|T|$ であれば多重分離問題と一致する.

そして多重目標点分離問題に対して, 最99
適解の $2(1-1/k)$ 倍以内の重みをもつ分割を求め

端点が異なる成分に含まれる辺の集合,

るアルゴリズムを提案する.

を分割 $R$ の重みとする. 即ち,$E(R)\equiv\{(u, v)\in E|u\in V_{\mathfrak{i}},$$w(R)$$v\in V_{J}\cdot,$$i\neq j$

定義$2$$w(R) \equiv\sum_{\epsilon\in E(A)}w(e)$$G=(V, E)$ を節点集合 $V$ および辺集合 $E$ を持っ
単純無向グラフ (非連結グラフであってもよい) とする. 節点

と

$x$

$y$

と定義する.

を端点とする辺を $(x, y)$ と書く.

$(G, w)$ をグラフ

$G$

の各辺

$e$

に正の実数値の重(4) 分割の和;

み $w(e)$ を持っネットワークとする.

$R_{1},$ $R_{2},$(1) 分割;$V$$V/R$ は

$R_{1}\wedge R_{2}\wedge\cdots\wedge R_{k}$を分割,$W\subseteq V$$V_{1},$

分と呼ぶ.

また,

$V_{k}$$\ldots,$

を $V$ の分割 $R$ による成

(5) 分割の強弱;$R_{1}$

上のすべての分割$R$と$R_{2}$を$V$

上の 2 っの分割とこのとき, 任意の $x,$ $y\in V$ に対して,

する.

$xR_{1}y$$V$$\wedge kR_{h}$に対して $W/R$ を $W$ の $R$ にと記す.

トと呼ぶ.

$|V/R|=$ たなる

ならば$xR_{2y}$の集合であるとき,

を $\Omega(k, V)$ で表す.

(2)

あるいは

$h=1$

$|V/R|=2$ である $V$ 上の分割 $R$ をとくに $V$ のッ,による商集合である. 本研究を通じて,

よる分割,

カ

に対して

により定義される $V$ 上の分割を簡単にとなる同値関係 $R$ を考える. ただし,

$R$

$R_{k}$$\ldots,$

つかの分割

く

$xRyrightarrow(xR_{1}y)\wedge(xR_{2}y)\wedge\cdots\wedge(xR_{k}y)$$V/R=\{V_{1}, \ldots, V_{k}\}$

$R$

上のい

の分割 $\{V_{1}, V_{2}, \cdots, V_{k}\}$ は同値関係 $R$を用いて表す. 即ち,

$V$ の

$V$

$R_{1}$

は$R_{2}$

より強い ($R_{2}$

は$R_{1}$より弱い) と言う.
$2$

節点の分離;2 節点 $x,$ がそれぞれ異なる分$y$割の成分に含まれるとき,$x\in V_{l},$

っまり,

3

問題

$y\in V_{J}\cdot(i\neq j)$

最小多重目標点分離問題とはネッ トワーク $(G=$であるとき,

$x$

と

$y$

とは分割 $R$ によって分離

において,

られたとき
$V$

目標点の集合 $T\subseteq V$ と $2\leq$

た $\leq|T|$ をみたす分割数と呼ばれる整数

されるという.

(3) 分割の重み;$(V, E),$ $w$ )の分割$V/R=\{V_{1}, \ldots, V_{k}\}$$R$による成分の集合

に対し $E(R)$ をその両$|T/R|\geq k$

$k$

が与え

100
を満たす $V$ 上の分割 $R$ で重み $w(R)$ を最小にする

TARGET の性能4.2ものを求める問題である.

TARGET により得られた $I(L)$ は次を満たす.

この問題は, 特に, $T=V$ の場合は多重分離間
題と, $k=|T|$ の場合には多重カッ ト問題と一致

任意の $i_{i}\leq h<i_{j+1}(i_{j}, i_{!+1}\in I(L))$ なる$k$に対して, $I(L)$ の作り方より明らかに,する.

本研究では TARGET, SPLIT という二っの近似アルゴリズムを考え,$T/ \bigwedge_{h=1}^{h}A_{h}=T/\bigwedge_{j_{1}h=}^{J}A_{h}$.

(2)

これらのアルゴリズムによって得られる分割の重みが, 最適値の $2(1-1/k)$

ここで,倍以内になることを示す.

$n(1)\equiv 1$,$n(j) \equiv|T/\bigwedge_{h=:_{1}}^{\mathfrak{i}_{J--\iota}}A_{h}|(j\geq 2)$

4

アルゴリズムと定義する.

4.1

アルゴリズムTARGET

定理 4.1 $n(l-1)<k\geq n(l)$ なる 1 に対し, 分割

ここでは多重分離問題に対する H. Saran とV. V. Varizani の近似アルゴリズム [7] を拡張した多項式アルゴリズムを示し,$\bigwedge_{h^{l}=i_{1}}^{1}A_{h}$口

それが最小多重目(証明) 最小目標点分離問題に対する最小重みの標点分離問題に対する近似解を求めることを示す.

分割$B^{*}$

とおく.

1.

$L$

:

$A_{1},$ $A_{2},$を $V$ のカット

を選び,

$V/B^{*}=\{V_{1}, V_{2}, \ldots V_{k}\}$TARGET

アルゴリズムは最適解の $2(1- \frac{1}{k})$ 倍以下の重みを持つ.

(1)$\ldots$$V_{j}$( $|V/A_{j}|=2$ なる分割) の集

ここで,} なるカット各$V_{j}$

に対し,$B_{j^{*}}\in\Omega(2, V)$$V/B_{j^{*}}=\{V_{j},$$V-$を考える. (1) における $\Omega(2, V)$ の重みの非減少順の列挙 $L$ : $A_{1)}A_{2},$$\ldots$に対し,

合 $\Omega(2, V)$ の重みの非減少順の列挙とする.

$V/A_{:_{j}}\cdot=V/B_{\dot{J}}^{*}=\{V_{j}, V-V_{J}\}$

2. 便宜上$A_{0}$

を $V$ 自身を 1 つの分割の成分とする(すなわち,

を満たす添え字ぢの集合を $I^{*}(L)=\{i_{J}^{*}|j=$分割とする.

$|V/A_{0}|=1$ なる)$1,2,$ $\ldots,$ $k$$|T/ \bigwedge_{h=0}^{i}A_{h}|>|T/\bigwedge_{h=0}^{i-1}A_{h}|$

なる添え字

$i$

の

} とする.

$|T\cap V_{J}|=1(1\geq j\geq k)$より明らかに集合を $I(L)$ とする.
$|T/ \bigwedge_{h=||}^{:_{j}}A_{h}|=j+1$$\{i_{1}, i_{2}, \ldots, i_{p}\}$3.

$(1\leq j\leq k-1)$

ステップ 2 で得られた $I(L)$ を$(i_{1}<i_{2}<\cdots<i_{p})$

として,

分割

を出力し終了.

$A_{L}= \bigwedge_{h^{p}=i_{1}}^{1}A_{h}$

さて, $I(L),$ $I^{*}(L)$ に対し, 上で定めた $\{n(j)|i=$$\square$1,$l$$\ldots,$} をもちいて101が成り立つ.

$J$$|T/ \bigwedge_{h=1})A_{1_{h}}|\geq n(j)+1$

,

られる分割

(3)

が成り立っことに注意する.

$w(A_{L})$

ここで,$i_{j}>i_{n(j)}^{*}$$\leq$$\sum_{j=1}^{l}w(A_{i_{j}})$$\leq$$\sum_{J^{=1}}^{k-1}w(A_{i};)$$=$$2w(B^{*})-w(A:_{k}\cdot)$

明らかに,

ここで,

は最適解

$A_{L}=A_{:_{1}}\wedge\cdots\wedge A_{\mathfrak{i}_{\mathfrak{l}}}$$|T/ \bigwedge_{h=1}^{J}A_{i_{h}}\cdot|n()\leq|T/\bigwedge_{h=1}^{i_{\mathfrak{n}(j)}}|$である.

TARGET によって得$B^{*}$の倍以下の重みを持つことを証明する.

$2(1- \frac{1}{k})$$|T/ \bigwedge_{h=1}^{J}A_{i_{h}}\cdot|n()=n(j)+1$

これにより,$\leq$と仮定すると (2) より$2(1- \frac{1}{k})w(B^{*})$( (4) より).

以上より定理 1.1 の証明が得られた.
$|T/ \bigwedge_{h=1}^{J}A_{i_{h}}\cdot|n()$$\leq$$|T/ \bigwedge_{h=1}^{n(j)}A_{h}|$$\leq$$|T/ \bigwedge_{h=1}^{j-1}A_{i_{h}}|$$=$$n(j)$

4.3

TARGET の実現

TARGET のステップ 1 において実際に全てのカッ トを列挙すれば $O(2^{n})$ の手間がかかってしまを得るが,これは (3) に矛盾する.

従って次の補題を得る.

TARGET に本質的に必要なカットだけをあらかじめ計算しておけば, ステップ 1

う.

以下では,

で全てのカットを列挙しなくても TARGET が望補題 4.1

みの出力が多項式時間で得られることを示す.

$i_{J}\leq i_{n(j)}^{*}(1\leq j\leq l)$$\Omega_{x,y}$

を $(G=(V, E),$ $w$ ) において

$x$

と

$y$

とを分

口

離するカットっまり,

上で $I(L)$$L$$I^{*}(L)=\{i_{1}^{*}, \ldots, i_{k-1}^{*}\}$

が対応する$A_{i\cdot n(g)}$$=$$\{i_{1}, \ldots, i_{l}\}$の分布との分布を考えたとき,

よりも列挙

$L$

$A_{i_{j}}$において早く現れる.

る.

各 $x,$$y$$R$

で重みが最小のカットの集合とすに対し, 任意のカット $C_{x,y}\in\Omega_{x,y}$ を $=$つ選んだ集合 $\{C_{x,y}|x, y\in T\}$ を考える.

補題 4.2$L_{T}$:$C_{1},$ $C_{2},$$\ldots$

を $\{C_{x,y}|x, y\in T\}$

任意の重み非減少順の列挙とする.

補題より,

各 $j=1,2,$$1$$\ldots,$に対し$w(A_{i_{J}})\leq w(A:_{\mathfrak{n}(j)})$テップ 1 でこの

$L_{T}$

このとき,

の
ス

を用いて得られる出力と同じ出力を与える全てのカット $\Omega(2, V)$ の列挙

$L$

が存

在する.
を得る. 従って(証明) 補題を示すためには,$w(A_{1})+w(A_{i_{2}})+\cdots+w(A_{1_{1}})$$\leq$$w(A:_{\mathfrak{n}(1)})+\cdots+w(A_{i_{n(k-1)}}\cdot)$$\leq$$w(A)+\cdots+w(A_{i_{-1}})$

列挙

$L$

カット

どんな $\Omega(2, v)$ のに対しても TARGET によって得られる$A_{1}\cdot(i\in I(L))$

は適当な二点 $x,$ $y\in T$ に

(4) 対し $A;\in\Omega_{x,y}$ を満たすことを示せばよい.

ある

102
の列挙に対しアルゴリズムによって得らる$\Omega(2, v)$

あるカッ ト$A_{i}(i\in I(L))$ を考えるの作り方より, 分割$R_{i-1}$の同じ成分に含まれ,
$u,$

$v$

$A$

アルゴリズム TARGET’

1. 目標点$T$を張る Gomory-Hu 木 $((T, F),$ ) を構

$A_{1}\wedge A_{2}\wedge\cdots\wedge A_{i-1}$

成する.

; によって分離される二点が存在するはずである.

$C_{u,v}$:. このとき,$I(L)$$\Omega_{u,v}$$c${$|e\in F$$R$。

} の重み $(c(e))$ の非減少

順の列挙を $L_{GH}$ : $R_{1)}R_{2},$$R_{|T|-1}$$\ldots,$とする.

の任意のカッ ト

2. 便宜上も$A_{0}$

を $V$ 自身を 1 っの分割の成分とする(すなわち, $|V/A_{0}|=1$ なる) 分割とする.

1T/(瓦_l\wedge$C_{u,v}$) $|>|T/R_{;-1}|$$|T/ \bigwedge_{h=0}^{j}A_{h}|>|T/\bigwedge_{h=0}^{1-1}A_{h}|$を満たすので,$L$が重みの非減少順に並んでいる

ことから,

なる添え字

3.

$w(A_{i})\leq w(C_{u,v})$である.

の集合を $I(L)$ とする.

ステップ 2 で得られた $I(L)$ を $\{i_{1)}i_{2}, \ldots, i_{p}\}$$(i_{1}<i_{2}<\cdots<i_{p})$即ち,$A_{:}$

ネッ トワーク

も$\Omega_{u,v}$

ロ

に属する

す重み付きの木 $((W, F),$
$u,$

$c$

口

Gomory-Hu 木の性質より, 各) である.

$v\in W$ 間の $(W, F)$ 上の唯一の道に含まれる枝の重みの最小値が $u,$

$v$

として,

分割 $A_{L}=A_{i_{1}}\wedge A_{i_{2}}\wedge\cdots\wedge A$ ; を出力し終了.

$(G=(V, E),$ $w$ ) に対する $W\in V$

を張る Gomory-Hu 木とは次の二っの性質を満た(1) 各節点対$i$を分離する最するカットで重み最小のものので表されるので. 列挙$L_{GH}$の中の 1 種である.

$x,$$y\in T$ を分離

1 っはカット$R$。

は補題 4.2 で考えた
よって補題 4.2 より,小カットの大きさを表す.

列挙(2) さらに,

TARGET’ で得られる出力は TARGET でも得ら$(W, F)$ からその最小値を与える枝を取り除く ことによってできる 2 っの連結成分が,
$u,$

$v$

$L_{T}$れる.

よって,

TARGET’ により得られる分割は最適解の 2–1/た倍以下の重みを持つ.

を分離する最小カットの成分を表す.

Gomory-Hu 木を利用することにより, TARGET’ は $O(|T|M(n, m))$ 時間時間で実行するこ
補題 4.3
在し,$W\in V$ を張る

Gomory-Hu 木は常に存$|W|-1$ 回最大流問題を解くことにより求Gomory-Hu 木 $((W, F),$ ) から 1 本の枝$c$

り除けば木は 2 個の連結成分に分かれ,成分に持っカット
とする.

$m$

辺からなる

ネッ トワーク上で最大流問題を 1 っ解くための時

口間で, 現在 $O(mn\log(n^{2}/m))$ 時間のものが知られめられる$c(e)$とができる. $(M(n, m)$ は $n$ 節点,$R_{e}$$e$

これらをが定義できる. R。の重みを

このとき$\{R_{e}|e\in F\}$

ている

[2]).

4.4

アルゴリズム

を取

を用いて,

SPLIT

ア文献 [7] にはもう 1 つの近似アルゴリズムが提ルゴリズム TARGET を次のように書き直すこと案されている.

ができる.

題に拡張することができる.

これも以下のように多重目標点問

103
アルゴリズム1.

SPLIT$w(D^{*})=w_{1}(D_{1})+\cdots+w_{k-1}(D_{k-1})$

を 1 つの分割の成分とする分割を$V$とする (である.

$D_{0}$

すなわち, $|V/D_{0}|=1$ ) ; $(G_{1}, w_{1}):=(G, w)$ .

2. $i=1,2,$
1.

$\ldots,$$k-1$ に対して以下を繰り返す.

$T/ \bigwedge_{h=0}^{i-I}D_{h}\{T_{1}, \ldots, T_{\iota}\}$$1\leq h\leq i$

において,

ある

明かに $w:(B_{j})\leq w(B_{J})$ である.

また,

$j=k,$ $k-1,$ $k-2,$

以下のようにして,

の順に添字

$j$

の列挙

:

$L_{B}\cdot$$1$$\ldots,$( $1\leq j\leq$ た) を決定して, 集合$B_{1},$ $B_{2},$$j(1\leq j\leq k-1)$$\ldots,$$B_{k}$

を作れば,$\Omega_{B}$

.

すべての

に対して $w_{j}(D_{j})\leq w_{j}(B_{J}\cdot)$ が成

立する.

に対し

1. $j=k$ について,$|T_{h}/D|=2$

ち,$|T_{j}/D|=1$$\Omega_{B}$. に含まれるカッ

重み最大のものを$B_{k}$

トのうとする.

$(j\neq h)$

2. $k-1\geq j\geq 1$ について,
即ち,$(G_{j}, w_{j})$

において,

を考える.

$|T/( \bigwedge_{h=0}^{i-1}D_{h})\wedge D|$

より$\Omega_{B}$除いた集合を$D_{j}$.

$\Omega_{B_{j}}$を決定するときのこと$B_{k},$$B_{k-1},$$\ldots,$$B_{g+1}$

を取り

とする.

$=|T/ \bigwedge_{h=0}^{1-1}D_{h}|+1$$|T/$が成立するカ ッ

ト

$D$

の中で

$(G_{\mathfrak{i}}, w_{1})$おける重み最小のものを$D_{h}’(1\leq h\leq i)$

小のものを

2.

$(G_{i}, w_{l})$$D_{i}$

から$D_{h}’$の辺を取り除いたとする$(1- \frac{1}{k})$$D_{1}\wedge\cdots\wedge D_{j-1}$の重みは最適な分割$B^{*}$$D^{*}$

ここで,

よりも弱
これを

$B_{j}$

口とすると$w_{\dot{J}}(B_{j})\geq w_{j}(D_{j})$定理 4.2 SPLIT によって得られる分割$D_{1}\wedge\cdots\wedge D_{k-1}$. の中には$\Omega_{B_{j}}$くないカッ トが存在する.

SPLIT の性能

4.5

$B_{j}^{*}|=j+1$$|T/(D_{1}\wedge\cdots\wedge D_{j-1})|=j$

より,$(G_{i+1}, w_{i+1})$.

$B_{\dot{j}}\epsilon\Omega_{B_{j}}$の中でさらに重みの最$E(D_{i})$$\wedge$

とする.

ととする.

ネッ トワークを

2

に

となる.

口

$=$

の重み の

以上のことより倍以下である.
$w(B_{1})+\cdots+w(B_{k-1})$(証明) $V/B^{*}=\{V_{1}, V_{2}, \ldots, V_{k}\}$ としたとき,
ト

;を

$B$

た集合
る.

$V/B_{J^{*}}\cdot=\{V_{j}, V-V_{j}\}$$\Omega_{B}$.

カッ$\geq$$w_{1}(B_{j-1})+\cdots+w_{k-1}(B_{Jk-1})$$\geq$$w_{1}(D_{1})+\cdots+w_{k-1}(D_{k-1})$$=$$w(D^{*})$であるカット, -まを $\Omega_{B}\cdot=\{B_{1)}^{*}B_{2}^{*}, \ldots, B_{k}^{*}\}$ であるとす

また, $w.(R)$ を $(G_{i}, w_{i})$ におけるカッ ト

重みとする.

このとき,

$R$ の

すなわち,

定理を得る.

口

104
4.6

SPLIT の実現

5.2

SPLIT のステップ 2 は,$T$

アルゴリズムOPTに対する $(G:, w,)$ 上アルゴリズム TARGET および SPLIT は共にGomory-Hu 木 [5] を構成すれば $O(|T|)$ 回の最適な分割の 2 倍以下の分割を求あることは示し

最大流問題を解く時間で実行することができる.

たが, 実際にどの程度最適な分割との差があるの全体として SPLIT は $O(k|T|M(n, m))$ 時間で実かを調べるためには最適な分割を求めそれとの比の$T=V$ の場合に較が必要である.

SPLIT の計算において $(G’, w’)$ の各成分の最ゴリズムを示す.

行することができる.
は

ただし,ここでは最適な値を求めるアル小カットは最小カットアルゴリズムを使って求められるので,[7] の $O(mn+n^{2}\log n)$ 時間の最小

カットアルゴリズムを使えば $(k(mn+n^{2}\log n))$
時間で SPLIT を実行することができる.

アルゴリズム OPT

1. 各節点を分割数と同じ数の成分に分けるすべての組み合わせを求める.

5

数値実験

2. 目標点の入っていない成分がある組み合わせ
を除き, その端点が異なる成分に含まれるよ5.1

試験問題の生成

本実験では,

うな枝の重みを合計しその組み合わせによる

ネッ トワークの節点数,

や分割数などの異なる試験問題に対してアルゴリ
ズム

分割の重みを求める.

目標点数

TARGET, SPLIT を適用して得られる分割

3.

ステップ 2 で求めた分割の重みの中で最小のものを最適な分割の重みとして出力する.

の大きさや, 実行時間の違いを調べてみた. 実験

では節点数と密度 (完全グラフに対する辺数の比)を与えて試験問題をランダムに発生させ, 各々に対してアルゴリズムを適用して比較を行った. 試
験問題は以下のようにして発生させた.

1. 節点数$n$, 密度 , 目標点数
$d$

$t$

, 分割数

5.3

OPT

と

TARGET

および

SPLIT との比較
アルゴリズム TARGET 及び SPLIT によって

$k$

を与

得られる分割の重さは最適なものの 2 倍以内であることは証明したがそれらの値が実際にどの程度える.

正しいかを調べてみた (表 1, 図 1). 節点数が 14

2.

$n$

個の節点

$v_{1},$$v_{2},$$\ldots,$$v_{n}$を作る.

3. 全ての節点間に確率 d% で重さ
さ$w$

以上の場合にっいてはアルゴリズム OPT の計算$w$の枝 (枝の重は 1 から 100 までの整数とする) を張り,

ネッ トワーク $(G, w)$ を作る.

時間が大きすぎて比較を行えなかった.
表の数字は各節点数ごとに 5 種類の異なるネットワークを作りアルゴリズムによって得られた分割の重みをアルゴリズム OPT によって得られた

4 節点$v_{1},$$v_{2)}\ldots,$$v_{t}$

を目標点とする.

最適値との誤差を百分率で表した.

$0$

は全く同じ

105
値を,

0.0 は異なる値を出したものの誤差が 1%以

行時間も大差なくほぼ同程度となっているこ
れは分割数が小さいためである.

下であったことを示す.

(3) 節点数, 目標点数を固定し分割数を変化させ

TARGET と SPLIT との比較

5.4た場合を表 4, 図 4 に示す.
分割数によってどちらのアルゴリズムを用いても枝が密なグラ

TARGET の実行時間は余

フに対しては全く同じ分割が得られることが多い.

り変化しないが SPLIT は分割数によって実これは密なグラフの最小の二分割は一点とその他

行時間が大きく変わる.

の点とを分ける分割であることが多いからだと思TARGET は $O(|T|M(n, m))$ 時間 SPLIT はわれる.

$O(k|T|M(n, m))$ 時間であるためである.

実際にアルゴリズムを適用した後の分割を見てみると多くの (ほとんどの場合はただ一つ

これは実行時間が(4) 結論の成分を除いて全ての) 成分は節点を一っしか含以上の結果より

まないことが多い.

分割の大きさについては SPLIT のほうが良そこでここでは密度の低いグラフについての比較を重点的に行った. 実験は節点数, 密度,い値であることが多いものの,

目標

どちらのアル

ゴリズムを用いても殆ど違いはない.

点数, 分割数の同じ問題を 5 問作りそれぞれに

実行時間については分割数が小さいと SPLITTARGET と SPLIT を適用して得られた分割の大の方が多少速いものの, 大きな分割数に対し

きさと実行時間についての比較を行った.

ては TARGET の方がかなり速くなる.

これは TARGET ではただ 1 回しか Gomory-Hu(1) 目標点数, 分割数を固定し節点数を変化させ木を張らないのに対して SPLIT では $k-1$ 回た場合を表 2, 図 2 に示す.

Gomory-Hu 木を張るからである.

以下で TARGET および SPLIT はそれぞれ以上のことから,のアルゴリズムによる値を示す.

TARGET の方が SPLIT よりも実用に適していると思われる.

しかし,

この実験においては SPLIT でも最小の 2 分

TARGET および SPLIT ともに実行時間は節割を求めるのに Gomory-Hu 木を用いたが,点数の増加にともない大きくなっているがどその代わりに [6] のアルゴリズムを用いればちらの実行時間も大差なくほぼ同程度となっ

SPLIT の実行時間についてより良い結果が得ているこれは分割数が小さいためである.

られていたと思われる.

(2) 節点数, 分割数を固定し目標点数を変化させた場合を表 3, 図 4 に示す.

TARGET および SPLIT 共に実行時間は目標
点数によって大きく変化するが,

どちらの実

6

まとめ
本研究では, ネットワークの分割問題において,これまで別個に扱われていた多重分離問題と多重

106
カ

ッ

ト問題とを,

多重目標点分離問題を考えて,同時に扱えるようにした. そして, 多重分離問題

で提案されていた最適解の 2 倍以下の重みを持つ分割を求める近似アルゴリズム拡張して, 多重目

標点分離問題で最適解の 2 倍以下の重みを持つ分割を求める近似アルゴリズムを提案した. そして,

, SIAM J. Algebraic and Discrete Meth$ods,$ $6,1985,$ pp.707-712.

$lem$[5] T. C. Hu; Integer programming and Network
Flows, Addison-Wesley Publishing Com-pany, 1969

チで最

[6] H. Nagamochi and T. Ibaraki, (Computing

適解の 2 倍以下の近似アルゴリズムを作るのは容edge-connectivity in multigraphs and capacitated graphs,” SIAM J. Disc. Math., 5, 1992,

他の分割問題に対しても, 同様のアプロー

易であると思われる.
今後の課題としては, 分割問題に対して別のアプローチを考え, 2 倍よりも良い近似解を求める

近似アルゴリズムを作ることを考えている.

pp.54-66.
[7] H. Saran and V. V. Vazirani; (Finding k-

cuts within twice the optimal, “ Proceedingsof $32nd$ Symposium on Foundations of Com参考文献$p$

窃 er Sicence, San Juan, Puerto Rico,

pp.743-751.
[1] E. Dahlhaus, D. S. Johnson, C. H. Pa-

padimitriou, P. D. Seymour and M. Yannakakis; “The complexity of the multiway
cuts,” Proceedings of the 24th $ACM$ Sym-

posium on Theory of Computing, Victoria,
Canada, 1992, pp.241-251.

[2] A. V. Goldberg and R. E. Tarjan, (A new ap-

proach to the maximum flow problem,” Journal of the $ACM,$ $35$ , 1988, pp.921-940.
[3] O. Goldschmidt and D. S. Hochbaum, “Poly-

nomial algorithm for thek-cut problem,”Proceedings of 29th Symposium on Foundations of Computer Sicence, Los Angels,
Calif., 1988, pp.444-451.
[4] D. S. Hochbaum and D. B. Shimoys,$O(|V|^{2})$(Analgorithm for the planar 3-cut prob-

1991,

107
表 1: 目標点数 $=$ 節点数, 分割数 $=3$ , 密度= $10\%$

表 2: 目標点数 $=50$ , 分割数 $=3$ , 密度 $=5\%$

表 3: 節点数 $=50$ , 分割数 $=3$ , 密度 $=5\%$

108$\xi AJ$$5\supset$

目標点数

図 3:節点数 $=50$ ,分割数 $=3$ ,

510

15

密度 $=5\%$

90
80
70

60
$\underline{\xi Q)}$50

$5\supset$$\triangleleft 0$

30

20
10
$0$

20

25

分割数
図 \sim :節点数 $=50$ ,目標点数 $=3$ ,密度= $5\%$

30

109

已
$–$
$5\supset$

図 1; 目標点数 $=$ 節点数,

分割数 $=3$ ,密度= $10\%$

図 2: 目標点数 $=50$ ,分割数 $=3$ ,密度= $5\%$$\xi Q)$$5\supset$