数理解析研究所講究録 1325 巻 2003 年 39-44

39
節点重み最大クリーク抽出アルゴリズム
An Algorithm for Finding aMaximum Cliquewith Maximum Vertex Weight
中村知倫, 富田悦次, 西野哲朗, 名久井行秀 (電気通信大学)
Tomonori Nakamura, Etsuji Tomita, Tetsuro Nishino, and Yukihide Nakui(The University of ElectrO-Communications)$\cdot$1

はじめに困無向グラフ中の最大クリークを抽出する問題は, 基本的で重要な組合せ最適化問題の一つであり,一層効難ではあるが, その効率的な厳密解アルゴリズムをこれまでに発表してきている ([1] 等). 更に最近,率化を達成したアルゴリズムも得ており [2], Discrete Applied Mathematics 誌 2002 年 8 月号にが発表した新しいアルゴリズム [3] に対しても非常に高速であることを確認している [4].
このアルゴリズ を適用することにより, バイオインフオマテイクス [5], 画像処理 [6], 分子計算における DNA あるいは RNA 配列の設計 [7] 等の実問題解決の有効な結果を得ている. 更に, この様な実問題処理においては枝に重みを考慮することも重要となり, それに対応した最大クリーク抽出アルゴリズムも開$\mathrm{N}\mathrm{P}$$\ddot{\mathrm{O}}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{g}^{\mathrm{Q}}\mathrm{a}\mathrm{r}\mathrm{d}$$\text{ム}$発している [8].

ところで, 量子論理回路の深さを最小化する問題も最大クリーク問題へ還元することが可能であり [9], この場合には節点に重みを考慮することが必要となる. 従って本稿においては, 節点に重みを持ったグラフを対象とし, 最大サイズクリークの中で節点重みの総和が最大であるクリークを抽出する一般的なアルゴリズムを提唱する. 更に, これをランダムグラフ, DIMACS ベンチマークテスト用グラフ, 及ひ量子論理回路を還元したグラフに適用して, 実験的にその性能評価を行った.

1.1

諸定義及ひ記法を枝の集合とするとき, 対象とする無向グラフを $G=(V, E)$ で表す. 2 節
点幻間の枝は非順序対 $(i,j)=(j, i)$ で表し, このとき節点 と は隣接しているという. ここで対象とする無向グラフでは, 自己閉路や多重枝は含まないものとする.
で表す. 一般に集合 の要素数を $|S|$ で表し,
グラフ $G$ において, 節点 に隣接する節点の集合をを節点 の次数と呼ぶ.
グラフ $G=(V, E)$ において, $V$ の部分集合 $S$ によって誘導される部分グラフを $G(S)=(S, E\cap(S\mathrm{x}S))$と表す. 以後部分グラフと記述した場合, それは誘導部分グラフを指す.
$G$$V$ の任意の 2 節点が隣接しているとき, 即ち $\forall i,j\in V,$ $i\neq j$ に対して $(i,j)\in E$ であるとき, グラフは完全であるという. $V$ の部分集合 $C$ において $G(C)$ が完全であるとき, $C$ をクリークと呼ぶ. なおかつ,それが他のクリークの真の部分集合でなければ極大クリークと呼ひ, 対象とするグラフ $G$ 中で節点数が最又は単に で表し,大の極大クリークを最大クリークと呼ぶ. グラフ $G$ 中の最大クリークの節点数を$V$を節点の集合,$E\subseteq V\mathrm{x}V$

$i$

$v$

$|\Gamma(v)|$$\Gamma(v)$

$j$

$S$

$v$

$\omega(G)$$\omega$

グラフ $G$ 中の最大クリークの個数を $N(\omega)$ で表す.
グラフ$V$ の部分集合 $C$ において任意の 2 節点が互いに隣接していないとき, $C$ を独立節点集合と呼ぶ.

中の全節点を最も少ない数の独立節点集合に分割することを彩色と言い, 同じ独立節点集合に含まれる節点は同じ色であると言う. この彩色を行うと, 隣接する節点同士には必ず異なる色が付与されて ること こなる. 彩色可能な最も少ない色数を彩色数と呼ぶ.
節点 に付与された節点重みを $w(v)$ , 節点集合 $V$ 内の各節点の節点重みの総和を $w(V)$ で表す.
」$-$
グラフ $G$ 中の最大クリークの中で, 節点重みの総和が最大となる部分集合を節点重み最大な最大クと呼ぶ. 本稿ではこれ以降, 節点重み最大な最大クリークを略して節点重み最大クリークと呼び, 節点重$\mathrm{A}\grave$

$v$

$1$

$\text{ク}$40$b\ovalbox{\tt\small REJECT}\lambda P^{\mathrm{I}}\mathrm{J}-\sigma\epsilon \mathrm{f}\mathrm{f}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{T}\xi_{\}}\ovalbox{\tt\small REJECT}_{\mathrm{p}}7\ovalbox{\tt\small REJECT} \mathrm{g}\mathrm{g}_{\lceil^{t}}\mathrm{J}_{J1\backslash \backslash }\Xi\ovalbox{\tt\small REJECT} b\ovalbox{\tt\small REJECT}\star ff\mathrm{I}]-\mathit{5}$2アルゴリズム21

最大クリーク抽出アルゴリズム

ffi$\mathrm{f}\mathrm{l}7.5\mathrm{F}\ \#\backslash \exists^{\mathrm{i}},\zeta_{\backslash }^{\backslash ^{\backslash }}$.

文献 [1] では, 最大クリーク抽出アルゴリズム MCLIQ(または) を提唱している. このアルゴリズム
は, 深さ優先探索により最大クリークを 1 個抽出する. この探索を効率的に行うため, 近似彩色に相当する
手続き NUMBERING-ARRANGING を行うことで, 各節点ごとのクリークの節点数の上界を高速に求め,を基本アルゴリズムとして, 目的とする節その上界により分枝限定を行っている. 本稿では, まずこの$\mathrm{M}\mathrm{C}$$\mathrm{M}\mathrm{C}$

点重み最大クリーク抽出アルゴリズムを構築する.

2.2

基本アルゴリズム1: procedure VWMC(G $=(V,$ $E)$ )2: begin, Qmaz;global3:
global $w(Q):=0,$ $w(Q_{\max}):=0_{j}$4:Sort vertices of in noteincreasing order5:with respect to their degrees;
6:
NUMBERING-ARRANGING(V,No)j7:
EXPAND-VWC ( $V$ ,No) ;8:
output $Q_{\max}$
9:
10: end {of VWMC}$Q:=\emptyset$$:=\emptyset$$V$

図 1: アルゴリズム VWMC

アルゴリズム$\mathrm{M}\mathrm{C}$において, 候補節点集合 $R$ における分枝条件は,

lQl+Max{No(p)lp\in R}>lQm。xl(1)である. ただし, $Q$ は現在の探索で保持しているクリーク, Qmaoe は現在までに抽出されている最大クリーに付けられた番号とすると, その最大値は候補節点集合内のクリークの節点数の上界である. しかし節点重み最大クリークでは, グラフ中に最大クリークが複数存在する
場合, それら全てについて重みの総和の比較を行う必要がある. そこで分枝条件をクである. No(p) を近似彩色によって節点$p$|Q|+Max{No(p)|p\in R}\geq |Q、a2|(2)とすることで, $Q_{\max}$ と同じ節点数の極大クリークであっても抽出できるようにする. この分枝条件を用いるアルゴリズムを VWMC とする. 図 1, 2 がアルゴリズム VWMC である.
ただしこの方法では, 探索中に最大クリークが見つかるまでは本来探索する必要のない節点も探索されてしまうことになる. そこで が既知の場合は, 式 (2) の分枝条件中の $|Q_{\max}|$ をに変更することで, 無$\omega$$\omega$駄な探索が行われずに済む. このようにして探索を行うアルゴリズは, 最大クリーク抽出アルゴリズ を用いて を求めてから,と記す.
合,$\text{ム}$$\omega$$\text{ム}$を$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}\omega$とする.
が未知の場合を適用する. この方法を用いる場$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}\omega$$\omega$$\mathrm{M}\mathrm{C}+\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}\omega$

2.3

重みの上界による分枝限定

前記のアルゴリズムでは, 対象とする無向グラフ中に複数個存在する最大クリークを全て抽出して, その中で節点重みの総和が最大であるものを 1 個選んでいたが, このような方法を用いると, 最大クリークの個数が多くなると最大クリークを 1 個だけ抽出するよりも抽出に必要な時間が増大してしまう可能性がある.
この問題を解決するために, 候補節点のクリーク重みの上界を高速に求める方法を考える.

41
1:
2:
3:
4:

5:
6:
7:

procedure EXPAND-VWC ( $R$ ,No)
begin
while
do
vertex in $R$
such that No(P)=Max{No(q)lq\in R};
if $|Q|+No(p)\geq|Q_{\max}|$ then$R\neq\emptyset$$p:=\mathrm{a}$$Q:=Q\cup\{p\}$ ;$w(Q):=w(Q)+w(p)$ ;

8:
9:
10:
11:
$12$

$R_{\mathrm{p}}:=R\cap\Gamma(p)_{j}$ifthen$\mathrm{N}\mathrm{U}\mathrm{M}\mathrm{B}\mathrm{E}\mathrm{R}1\mathrm{N}\mathrm{G}- \mathrm{A}\mathrm{R}\mathrm{R}\mathrm{A}\mathrm{N}\mathrm{G}1\mathrm{N}\mathrm{G}(R_{p},No’)j$( ,No’)
else if $w(Q)>w(Q_{maz})$ then:$\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{A}\mathrm{N}\mathrm{D}- \mathrm{V}\mathrm{W}\mathrm{C}$

13:
14:

$Q_{ma\varpi}:=Q$$R_{p}$;$w(Q_{\max})\mathrm{f}\mathrm{l}:=w(Q)$$1615.\cdot.\cdot$

17:
18:
19:

$R_{\mathrm{p}}\neq\emptyset$

flfi$Q:=Q-\{p\}$ ;$w(Q):=w(Q)-w(p)$ ;20:$R:=R-\{p\}$
21:
od
22:
23: end{of EXPAND-VWC}

図 2: 手続き EXPAND-VWC

ある候補節点集合に番号付けを行った結果が $\mathrm{M}\mathrm{a}\mathrm{x}\{No(p)|p\in R\}=maxno$ であり, 付けられた番号ごとの独立節点集合が$Ci=\{p\in R|No(p)=i\}$ ,( $i=1,2,$$\ldots$, maxno)(3)であるとする.

任 意の候補節点集合 $R$ 内に番号付けが行われた後, 番号が大きいほうから順に次の深さへの探索が行われていき, その節点における探索でより大きなクリークが見つからない場合 $R$ 内から削除する, という作業をとなるまで繰り返している. 従って, 次に探索する節点の番号が であるならば, 残りの候補節点の番号は 以下となる. クリークは異なる番号の独立節点集合から節点が 1 個ずつ選ばれて構成されるの$\circ$$R=\emptyset$

$k$

$k$

で, それぞれの独立節点集合内の重みの最大値の合計値がクリーク重みの上界となる. これを利用すると,番号が である節点のクリーク重みの上界は,$k$$UWC_{k}= \sum_{i=1}^{k}{\rm Max}\{w(p)|p\in C_{i}\}$と表すことができ, 式 (4) の重みの上界を用いると,$|Q|+{\rm Max}\{No(p)|p\in R\}\geq\omega$

式 (5) の分枝条件を用いるアルゴリズムを3( $k=1,2,$$\ldots$(4),maxno)が既知の場合, 次のような分枝条件が考えられる.

(5)$w(Q)+UWC_{{\rm Max}\{N\circ(\mathrm{p})|p\in R\}}>w(Q_{\max})$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$とする.

計算機実験
今回提唱したアルゴリズ VWMC,, 更に最大クリーク抽出アルゴリズ
言語を用いて実働化した. コンパイルは gcc-02 で行った. 使用した計算機はは Linux である.
$\text{ム}$$\mathrm{C}$and$\omega$,$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega},$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$$\text{ム}$$\mathrm{M}\mathrm{C}$を$\mathrm{C}\mathrm{P}\mathrm{U}:\mathrm{P}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{u}\mathrm{m}42.2\mathrm{G}\mathrm{H}\mathrm{z}$,$\mathrm{O}\mathrm{S}$3.1

ランダムグラフ

グラフは, 各節点に確率 の一様乱数で枝を張って作成したグラフである. 節点数 , 枝密度 の各組み合わせごとに, 乱数の seed として 1 から 10 の正整数を与えることでランダ グラフを 10 個用意しランダ$\text{ム}$$n$$p$$\text{ム}$$p$

42た. 次に, 作成したランダムグラフの各節点に節点の重みとして, 節点数の 10 分の 1 を重みの最大値として1 から (重みの最大値) までの整数値を, 各節点に一様乱数的に与える. このような条件で作成したランダムグラフの各節点に重みを付与したものを各グラフ 1 個ずつ用意した. アルゴリズムを実行する際には, あらかじめ が判明している必要があるので, 前処理として最大クリーク抽出アルゴリの実行時間は考慮に入れてズム MC を用いて を求めその結果だけを利用した. (即ち, この場合にはいない. )の実行時間を表 1 に示す. なお, 表には 10 個のグラフの平アルゴリズム VWMC,均値を載せた. 比較のため, 節点重みを考慮しない場合の MC の実行時間も載せた.
$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega},$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$$\omega$$\mathrm{M}\mathrm{C}$$\omega$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega},$

3.2$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$

DIMACS ベンチマーク用グラフ

DIMACS で提供されているベンチマーク用グラフは節点重みなし無向グラフである. そこで, ランダムグラフの場合と同様に各節点の重みとして, 節点数の 10 分の 1 を重みの最大値として, 1 から (重みの最大値) までの整数値を, 一様乱数に従って与えたものを, それぞれ 1 個ずつ用意した.
, VWMC 訝の実行時間を表 2 に示す.
DIMACS ベンチマーク用グラフに対する VWMC,$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$

4333

量子論理回路を還元したグラフ

量子論理回路を還元した節点重み付き無向グラフの実行結果を以下に示す. 無向グラフとして, 文献 [10]表 1 のグラフを, 表2のグラフをのように表す.とし, 表の上から順に $G_{1}(1),$ $G_{2}(2),$
実験結果を表 3, 4 に示し, 更に詳細は文献 [10] に示す. ただし, この実験で使用した計算機は文献 [10] との 2 変数論理関数の場合 (表 1), 3 変数論理関数の場合 (表 2) のデータを用いた.
$G_{2}$

同じ$G_{1}$$\cdots$$\mathrm{C}\mathrm{P}\mathrm{U}:\mathrm{P}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{u}\mathrm{m}42.8\mathrm{G}\mathrm{H}\mathrm{z}$である.

表 4: 3 変数論理回路の場合に対する実行時間 $[\sec]$
表 3: 2 変数論理関数の場合に対する実行時間 $[\sec]$$n=208,$ $p=0.946860$$n=40,$ $p=0.80000$

4

考察
ランダムグラフに関しては, アルゴリズのそれと比較して, $N(\omega)$が非常に大きい場合を除いて 25 倍程度以内に実行時間が抑えられている. このようなグラフに関してで解を求めるよりも VWMC を用いて解を求める方が, 全体的に見て実行が未知の場合は,時間が速いことが表より分かる. しかし枝密度が大きく $N(\omega)$ が非常に大きくなると, VWMC,$\text{ム}$VWMC,$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\cup}$の実行時間は$\mathrm{M}\mathrm{C}$$\omega$$\mathrm{M}\mathrm{C}+\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\mathcal{O}}$では, MC と比較してやはり実行時間は大幅に増大する場合が多い.
アルゴリズ VWMC 訝は,と比較して実行が小さい場合にはあまり効率的ではな時間が増大してしまう場合が多いが, 実行時間の増大は高々 12 倍程度に抑えられており, 実行時間の増大が大きいグラフでは, クを極力抑える, という点では成功していると言える. 一方, 枝密度力状きくリーク重みの上界による分枝限定が効果的に働き, 実行時間の大幅な短縮ができている場合が多い. しかが大きいグラフでも枝密度が小さいグラフの中にはクリーク重みの上界による分枝限定の効果がし,あまり見られないものがいくつかあるが, これは NUMBERING-ARRANGING という手続きは枝密度が大きい方が番号の最大値をより小さく抑えるという性質があるので, 枝密度が小さい方てはクリーク重みの上界が大きくなってしまうためであると考えられる.
DIMACS グラフは枝の張り方に偏りがあるグラフであるが, 実行時間の比較を行うとランダムグラフのが非常に大きい時と同様の傾向が見られる. 特に注目すべきは, 枝密度力状きくランダ グラフよりでは大幅に実行時間が増大する. こやグラフで, このようなグラフでは, MC と比べてではクリーク重みの上界による分枝限定が効果的に行われ, 大幅なのようなグラフに対して,では, 24 時間以上というグラフは VWMC や実行時間の削減に戒功している. 特にを用いて 6 時間程度で解を抽出することがでかかつても解を抽出することができなかったが,$\text{ム}$$N(\omega)$$\text{く},$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$$N(\omega)$$N(\omega)$$\text{ム}$$\mathrm{W}\mathrm{M}\mathrm{C}$$N(\omega)$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{4},+$$\mathrm{M}\mathrm{A}\mathrm{N}\mathrm{N}_{-}\mathrm{a}27$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$

きた.

量子論理回路を還元して生成した無向グラフについては, MC と VWMC の実行時間の比較のみを示した. 表 3 のグラフは $N(\omega)$ が小さいが, VWMC の実行時間が MC の実行時間の 5 倍程度となっている. これは MC の探索過程で最初に発見される極大クリークが最大クリークとなり, 分枝限定が効果的に働きそ44れ以降の探索をしなくてすむのに対して, VWMC では複数個抽出しなければならないためであると考えられる. 表 4 のグラフについては VWMC の実行時間が MC の実行時間の 10,000 倍程度となっている. これが非常に大きいグラフであるためと考えられる. ただし, この場合にははの大きい有効性が発揮される [10].
$N(\omega)$

5$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$まとめ

本稿では, 節点重み最大クリークを抽出するアルゴリズムを提唱し, 実働化して実行時間を比較することにより, アルゴリズ の評価を行った. 実験結果から,が非常に大きい場合を除けば, アルゴリズム
VVVMC, VWMC, を用いることで, 最大クリーク抽出アルゴリズムの数倍内程度の実行時間で, 節点重みでは MC と比べて実行時間が大幅最大クリークが抽出できることを確認できた. また, VWMC,アルゴリズムが有効であることを実験的に確認した. 更に増加してしまうグラフについては,に, 本アルゴリズ を量子論理回路深さ最小化問題に適用した [10].
量子論理回路深さ最小化問題をクリーク問題に還元する場合, 枝密度が非常に大きくなる. 枝密度が大きいグラフに対して効率的な重みなし最大クリーク抽出アルゴリズム等は既に得ているので, 今枝密度が大きい場合の効率化を目指す.
後, これらの基本アルゴリズムも考慮し,
なお, 本研究は, 電気通信大学研究・教育活性化支援システムの支援を受けている.
$\text{ム}$$N(\omega)$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$$\text{ム}$$\mathrm{M}\mathrm{C}\mathrm{Q}\mathrm{d}^{+}[2]$

参考文献[1] 富田悦次, 今松憲一, 木幡康弘, 若月光夫: “最大クリークを抽出する単純で効率的な分枝限定アルゴリ
ズムと実験的評価,” 電子情報通信学会論文誌, vOl.J79-D-1, no 1, pp.221-228 (1996).
[2] 関友和, 富田悦次: “分枝限定法を用いた最大クリーク抽出アルゴリズムの効率化,” 電子情報通信学会
コンピューテーション研究会, COMP 2001-50, pp.lO1-108(2001).
[3] P. R. J.

$\ddot{\mathrm{O}}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{g}^{\mathrm{o}}\mathrm{a}\mathrm{r}\mathrm{d}$: “A fast algorithm for the maximum clique problem,” Discrete Appl. Math. 120,

PP.197-207 (2002).
[4] E. Tomita and T. Seki: “An efficient branch-and-bound algorithm for finding amaximum clique,”Proc. Discrete Mathematics and Theoretical Computer Science 2003, LNCS (2003, to appear).
[5] D. Bahadur K. C. , T. Akutsu, E. Tomita, T. Seki, and A. Fujiyama: “Point matching underuniform distortions and protein side chain packing based on an efficient maximum clique algorithum,”
Genome Informatics, 13, pp. 143152 (2002).

$\mathrm{r}_{1}\mathrm{o}\mathrm{n}-$[6] 堀田一弘, 富田悦次, 関友和, 高橋治久: “最大クリーク抽出を用いた画像からの対象検出, ” 情報処理学会数理モデル化と問題解決研究会, 2002-MPS-42, PP. 49-56(2002).
[7] S. Kobayashi, T. Kondo, K. Okuda, and E. Tomita: “Extracting globally structure free sequences bylocal structure freeness,” Proc. International Meeting on DNA Based Computers (2003, to appear).

[8] 鈴木純一, 富田悦次, 関友和: “枝重み最大クリーク抽出アルゴリズム,” 2002 年度夏の LA シンポジウ
ム, no. 17(2002).

[9] 名久井行秀, 西野哲朗:“量子論理回路深さ最小化問題のクリーク問題への還元,” 情報処理学会数理モ
デル化と問題解決研究会, 2002-MPS-42, pp. 57-60(2002).
[10] 名久井行秀, 西野哲朗, 富田悦次, 中村知倫: “節点重み最大クリーク抽出に基づく量子論理回路の深さ最小化,” 2002 年度冬の LA シンポジウム, no. 91-97(2003).