数理解析研究所講究録
第 1744 巻 2011 年 169-176

169

最大クリーク問題の多項式時間的可解性について
富田 悦次 \dag er

中西 裕陽*

1

西野 哲朗 \S

若月 光夫 \d ag er

次の定量的一基本結果を示した [4].

まえがき

「節点数 の–oe グラフにおいて，最大次数 が対象グラフ中に所定サイズのクリークが存在する $\Delta\leq 2.495dlgn$ $(d\geq 1:$ 定数 なる条件を満たしてか否かを判定する最大クリーク問題は，典型的な NP いる時，このグラフの最大クリーク問題は $O(n^{2+d})$完全問題であり，多項式時間的に本問題を解くこと なる多項式時間で可解である．
」
はほぼ不可能であると強く予測されている [1], [2].
さらに，その定量的改良として，次の結果を与え$\Delta$$n$$)$

ここで，パーフェクトグラフ [3] 他，幾つかの特殊グ

ラフにおいては最大クリーク問題が多項式時間的に可解であることが明らかにされている (文献 [4] 中の文献参照). ただし，これら特殊グラフに対してた [7].

「節点数

$n$

の-

$\mathfrak{R}$

グラフにおいて，最大次数$\Delta\leq 2.613dlgn$ $(d\geq 1:$$\Delta$が定数 なる条件を満たして$)$いる時，このグラフの最大クリーク問題は $O(n^{1+d})$

最大クリーク問題が実用上高速に解くことが可能となる多項式時間で可解である．
」
は必ずしも限らない (たとえば，文献 [3] では，8.
なお，上記においては，グラフは隣接行列表現 (デーConclusion として，Althoug these algorithms are タ構造) を用いることを前提としていたが ([7], 4 章，
polynomial (and thus are theoretically good) we do P33, 右，4 行目), 全体的明示が欠けていたので，
not recommend them for practical use. と記述されここに改めてその前提を追記する．ここで，文献 [4]ている).

の基本結果から文献 [7] への改良は，“部分問題の統これに対し，特殊グラフについてではなく，一般 合による探索領域削減” という新たな手法の導入によ
グラフに対して出来る限り自然で緩やかな条件とし る探索領域削減の達成によっている．
て，どの様な場合ならばこの NP 完全問題が多項式
本稿においては，“部分問題の統合による探索領
時間的に可解と証明出来るかを示すことは，この他 域削減’ をより詳しく解析することにより，更に探索
幾多の NP 完全問題との関連においても重要な問題
領域の削減を進め，新たに次の結果を与える．
$\acute$となる．

「節点数 の一般グラフにおいて，最大次数$n$これに沿った具体的定量結果として，- グラフにおいて，まず最大次数 が定数である場合に，最大ク$\mathbb{R}$$\Delta\leq 2.704dlgn$ $(d\geq 0:$$\Delta$が定数 なる条件を満たして$)$$\Delta$

いる時，このグラフの最大クリーク問題は $O(n^{1+d})$リーク問題は，節点数 のグラフに対して $O(n\log n)$ なる多項式時間で可解である．
」$n$時間で可解であることが発表されている [5].
ここでは，グラフの次数に関する条件の定数部分を
また，筆者らは，節点数 のグラフ中の極大ク 2.613 から 2704 に増大させると共に，定数 に対すリークを $O(3^{n/3})$ 時間で全列挙するアルゴリズム$d\geq 1$ から $d\geq 0$ へと拡張している．後る条件を，
CLIQUES[6] を基礎として，-ff グラフにおいて．最 者の拡張は，グラフの表現を隣接行列とするとの前大次数 が節点数 の対数オーダである場合に，最提を撤廃する (即ち，隣接リストを用いる) ことに大クリーク問題は多項式時間的に可解であることの， より得ている．
$n$

$d$

$\acute$$\Delta$$n$” 電気通信大学先進アルゴリズム研究ステーション
電気通信大学先進アルゴリズム研究ステーション: 中央大学$\dagger$

研究開発機構$*$電気通信大学先進アルゴリズム研究ステーション: 電気通信

大学情報理工学研究科\S 第 3 著者に同じ

本論文のアルゴリズム，解析手法は，文献 [6], [4],[7] を直接的基盤としており，重複した記述は出来る限り省略している．従って，必要に応じて適宜前出
文献を参照いただきたい．

170
2を加えた，深さ優先探索の分枝限定アルゴリズムと諸定義と記法
本稿で対象とするグラフは: 自己閉路をもたない$V$ は節点無向グラフ $G=$ $(V. E)$ とする．ここで，している．

部分森の同一化は，与えられた入力節点集合
SUBG に対して．その最大次数節点 を先頭とし$u$の有限集合， は相異なる 2 節点の非順序対 $(V, w)$て先に探索を行うことにより． の隣接節点集合(これを枝と呼ぶ) の集合である．節点 とは．，$SUBG_{u}=SUBG\cap\Gamma(u)$ 中の各節点については$(v,w)\in E$ が成り立つとき隣接しているという．
探索を省略する，Bron-Kerbosch[8] におけるのと同集合 に対して，その要素数を $|V|$ で表す．また，$E$$\acute$$u$$v$$\acute$$w$$V$

集合 $V$ が順序付き集合である時，その先頭から$i$

番目の要素を $V[i]$ で表す．

.

$v\in V$について，$|\Gamma(v)|$を$v$$V=\{v_{1},v_{2}, \ldots,v_{n}\}$による探索においては，探索候補節点集合
$u$

として，

SUBG,$A=SUBG\cap\Gamma(u)$ ,
および，

に対して，

$EXT_{l}=SUBG-\{u\}-SUBG_{u}$を定める．更に，この , および EXTr、中の各節点と定義する．

$u$$Q\subseteq V$の誘導部分グラフ $G(Q)$ に対$G(Q)$ はクリークであるとして，次が成り立つとき，$\forall_{V.W}\in Q(v\neq w)$に対して $(V., w)\in E$$u,v_{1},v_{2},$ $\ldots,v_{|F_{l}XT_{u}}$Iに対して，それぞれ隣接部分,

いう．

$SUBG_{u,}.SUBG_{1},$ $SUBG_{2,\prime}|,\ldots.SUBG_{\tau_{|r,x\cdot\tau_{u}|}}$.

このとき単に， はクリークであるともいう．
$Q$

節点の部分集合 $W\subseteq V$ による誘導部分グラフ$G(W)$ 中の最大クリークのサイズ (節点数) を $\omega(W)$で表す．

3

探索領域の単純削減

SUBG 中の最大次数節点をの次数と呼ぶ．

$\Gamma(V)=\Gamma(v_{1})\cap\Gamma(v_{2})\cap\ldots\cap\Gamma(v_{n})\wedge$

与えられた

3.1

$MCP_{1}’$$\Gamma(v)=\{w\in V|(v,\cdot w)\in E\}(\geq v)$

と定義し，
また，集合

様の限定操作である．

が定義される．このとき節点$v_{i}$$SUBG-\{u, v_{1},v_{2}, , .., v_{i-l}\}$の先頭節点であり，は$SLBG_{\tau_{i}},=\Gamma(v_{i})\cap(SUBG-\{u_{:}v_{1},v_{2}, , .., v_{i-1}\})$

である．これらの隣接部分は上記の順序に従って探索を行なう．

の最後尾
このとき，
節点
の隣接部分について，次が成立する．
文献 [4] の基本アルゴリズム MCPO を拡張して，文参照．)
献 [7] のアルゴリズム MCPl を得ているが，本稿に [補題 1](文献 [4], [補題 1]

改良アルゴリズム $MCP_{1}’$$EXT_{u}=\{v_{1},v_{2}, \ldots,v_{|F,XT_{u}|}\}$$v_{|F_{J}XT_{u}|}$おいてはさらにそれを改良したアルゴリズムを提唱する．この基本部分を図 1 に示す．ここで，図$\omega(\{v_{|F_{J}X’\Gamma_{u}|}\}\cup SL^{\gamma}BG_{1},|P.XT_{u}|)\leq\omega(\{u\}\cup SL^{t}BG_{u})$$MCP_{1}^{l}$.

口

1 の 1600 行目におけるIの最後尾節点からの探索は行なわず，探索領域の単純な削減が出来る．

I $EXT_{1l}|-1$ とした時，文献 [4] のアルゴ

この様な探索領域の削減を，より強力化することを，次において考える．

これより，$EXT_{k1}$$i:=1$ to $EXT_{u}|-2$を$i:=1$ to

リズム MCPO(文献 [4], 図 1) とほぼ同じであり，深さ優先探索手続き EXPAND の適用により，サイズ 0 のクリークから出発して，より大きいクリーク
$()$

3.2

$v_{|F_{J}XT_{u}|}$部分問題の統合による探索領域削減

である場合において，に改良アルゴリズム MCP; の基本部分全体は， $EXT_{u}$ 中の最後尾から 2 番目の節点ついて考察する．
MCPO と同様に，下記の限定操作[補題 2] $(|F_{J}XT_{u}|-\iota\cdot|F_{J}XT_{u}|)\not\in E$ であるならば，部分森の同一化を逐次求めてゆく過程が主体である．

$|EXT_{u}|$以下では，$\geq 2$$v_{|F_{J}X\text{鑑}|-1}$(文献 [4] においては，33
最後尾節点の探索省略)

探索領域の単純削減$EXT_{\tau r}$$\omega(\{v_{|F_{J}XT_{u}|-1}\}\cup S\ddagger JBG_{|FXT_{V}|-1})$$SUBG_{u})$.

$\leq$$\omega(\{u\}\cup$

171
1400:
1500:
1600:
1700:
1800:
1900:
2000:
2100:
2200:
2300:
2400:
2500:
2600:
2700:
2800:
2900:

0000: Procedure $MCP_{\rceil}’(G)$0100: begin

0200: global $|Q|;=0_{:}$.
0300: global $|Q \max|:=0$ :EXPAND(V)0400:
0500: end {of MCP\’i}0600: procedure EXPAND $(SUBG)$
0700: begin0800:
if $9UBG\neq\emptyset$then $u:=a$ ve
0900:
in SUBG
that maximires $|SU\theta G\cap\Gamma(2l)||$1000:
ROOT: $=\{?l\}|$1100:
IQI $:=|Q|\cup|ROOT|$ ;1200:
SUBG. $:=\Gamma(\tau r.)\cap SUt?G_{:}$.
1300:$F_{J}XT_{u}:=19UFtG-\{u\}-SUBG_{u:}$.
$’\cdot te.x$

EXPAND $(SUt?G_{u})$
$|Q|$

.

$:=|Q|-|ROOT|_{:}$

for . $:=1$ to $|F_{J}XT_{u}|-2$$:=$ the first vertex in $F_{J}XT_{u}$ ;doROOT: $=\{n:\}$ ;$i$$?’ i$.

$S\Gamma JBC\prime v_{i};=\Gamma(\tau/;)\cap(F_{J}XT_{V}\cup SUBG_{u})$$|Q|:=|Q|+|BOOT|_{:}$.

EXPAND $(SUBC_{rv_{i}})_{:}$.

$|Q|:=|Q|-|ROOT|_{:}$$F_{J}XT_{u}:=F_{J}XT_{u}-\{\tau;_{*}\cdot\}$;

odelse $\{i.e., SUBG=\emptyset\}$if $|Q| \geq|Q\max|$then $|Q \max|$ $:=|Q|$fi
end {of EXPAND}

図 1: アルゴリズム MCPI(基本部分)
1301: if $|F_{J}XT_{u}|\geq 2$1302: and $(F_{J}X’\Gamma_{u}[|F_{J}XT_{u}|-1], F_{J}XT_{u}[|F_{J}XT_{u}]|])\in F_{J}$ then1303: ROOT $:=$ EXT. $[|F_{J}XT_{u}|-1],$ $F_{J}XT_{u}[|FiXT_{u}]|]\}$ ;1304:$SUP^{G_{TAtt}}\cdot:=$$\{$$\Gamma(\{F_{\ovalbox{\tt\small REJECT}}XT_{u}[|F_{\ovalbox{\tt\small REJECT}}XT_{u}|-1],$

if $|SUt?G_{TA,\Gamma}.|=|SUBG_{u}|-1$ then
1305:
;
1306:
SUBG.
fl
1307:
1308: fl

:

2401:
2402:
2403:

$F_{J}XT_{u}||F_{J}XT_{u}|]\})$$\cap(F_{\ovalbox{\tt\small REJECT}}XT_{u}\cup SUBG_{u})$;$|Q|:=|Q|+|ROOT|$EXPAND $(SUBG_{TArr},)_{:}$.
$|Q|:=|Q|-|ROOT|$$:=\emptyset$

図 2: アルゴリズム MCPI(探索領域削減)(証明) 文献 [7]:[補題 2] 証明参照．口集合$SUBG_{T\Lambda JJ,}$

この場合には，前節と同様にして，節点$=\hat{\Gamma}(\{EXT_{1A}[|EXT_{u}.|-1],$ $EXT_{ll}[|EXT_{\tau r}.|]\})$$v_{|F_{J}XT_{u}|-I}$からの探索も省略して，探索領域の単純削減を行う．

$\cap(SUBG-\{u,v_{1},v_{2}, \ldots,v_{|F,XT_{u}|-2}\})$

そうでない場合には，この節点からの探索を単純についてだけ探索を行えば十分である．

に省略することは出来ない．そこで，その様な場合の状況について考察する．乙 r$SUBG_{T\Lambda\Gamma\Gamma,}$$S$[補題 3]$\omega(\{v_{|F,XT}$

は，一般に$SUBG_{v_{|p,\chi\tau_{u1-\rceil}}}$および

よりサイズが小さい．即ち，次の補題が成り立っ．

$|-1\}\cup SLrBG_{|p,\chi\tau_{u1-\rceil}}\tau,)$。

[補題 4] 節点数 $|V|=n$ なるグラフ $G=(V, E)$$>\omega(\{u\}\cup SUBG_{t},.)$

なる不等式が成立するのは，$\{v_{|F_{J}XT_{u}|-1}\}$$SoeG_{\tau},|F\grave,X^{\prime r_{u1-\rceil}}$,$BG_{\eta_{|FrX\mathcal{T}_{V}|}}$

中の最大クリークが節点$v_{|p_{\ovalbox{\tt\small REJECT}}\chi}$

乳$\cup$$|$

をの最大次数を $\Delta\leq n_{-}1$ とする．節点の部分集合$SUBG\subseteq V$に対して．
$\acute$含む場合に限られる．

$|SUBG_{u}|=|SUBG\cap\Gamma(u)|=\Delta-k(0\leq k\leq\Delta)$(証明) 文献 [7]., [補題 3] 証明参照．口が最大となるとし
SUBG 中の節点をSUBG $-\{u\}-SUBG_{u}$$u$補題 3 から，以下に示す操作を導入することによ て，EXTn.
中に最大クリー $\{v_{1},vvx\tau$ $|-1,|F,XTu|$
り，{$=$$v_{|F,XT_{u|-\iota\}\cup SUBG_{v_{|F,x\tau_{u|-1}}}}}$

。

$=$

とする

このと

クが存在する場合，それらを検出することができる．き以下が成立する．
[1] もし $EXT_{kl}$ の最後尾 2 節点が互いに隣接しない
ならば，ならば，補題 2 によりの最後尾 2 節点の探索$|\Gamma(\{v|F_{J}x\tau_{u|-1},v_{|F_{J}XT_{u}|\})\cap SUBG|}\leq\Delta-k-1$ .
$(v_{|F_{J}x\tau_{u|-1}}, v_{|F,X\tau_{u1}})\in E$$\wedge$$EXT_{\eta}i$は単純に省略する．

(証明) 文献 [7]., [補題 4] 証明参照．口[2] 補題 3 中の不等式が成立のとき，$\{v_{|F,XT_{u}|-1}\}\cup$
補題 4 においては．集合のサイズのSUBG,,
中の最大クリークは節点$SUBG_{TAJ\Gamma_{J}}$の内容に
I を単純な上限を与えた．しかし，$SUBG_{T\Lambda\Gamma\Gamma,}$$\acute$$v_{|F_{J}XT_{u}}$$|\rho_{l}\chi\tau_{u|-1}$

含んでいなければならない．そこで最大クリークを関して詳しく考察することにより，さらに探索の削抽出するためには．あらかじめ節点$\acute$$v_{|F’,X^{r}\Gamma_{u}|}$を含む

減が実現出来る．

172$SUBG_{u}$図 3: 補題 5
まれない $SUBG_{u}$ 中の節点はただ 1 個存在する．こ先ず，以下の関係が成り立っ．
[補題 5] 節点数 $|V|=n$ なるグラフ $G=(V, E)$ の節点を とする．
いま $SUBG_{u}$ 中の最大サイズのクリークをの最大次数を $\Delta\leq n-1$ とする．節点の部分集合$r$$SUBG\subseteq V$に対して．

$C_{1},C_{2}\dot,$$\cdots,C_{k}(|C_{1}|$

$=$

...

$=$

$|C_{2}|$$\acute$$|SUBG_{u}|=|SUBG\cap\Gamma(u)|=\Delta-k(0\leq k\leq\Delta)$とし
SUBG 中の節点をSUBG $-\{u\}-SUBG_{u}$が最大となる$EXT_{2A}$
て，

$u$

$=$

$=$

$\{v_{1},v_{2,}\ldots.,v_{|F_{J}XT}$.

$\omega(SUBG_{2l}))$$[1|C_{1}$,

とおく．このとき節点$C_{2},$$(1\leq i\leq|EXT_{u}|)$$C_{k}$の全てに含まれる．

ない．

のいずれかを満足する．
$r$$C_{1},C_{2},$が [1] を満たす場合，含まないものの 1 個を Ci

および$SUBG_{\Gamma Af\Gamma,}’=\Gamma\wedge(\{EXT_{21}[|EXT_{\tau l}|-1]$,$SUBG_{T\Lambda\Gamma t,}$$\cap(SUBG-\{u, v_{1},v_{2}, \ldots,v_{|F_{J}XT_{u}|-2}\})$

従って

かつ

$|SUBG_{T\Lambda}rr_{J}|=\Delta-k-1$

のとき，

$r$

(証明).

$\ldots,C_{k}$のうち$(1 \leq i\leq k)$

$r$

を

とする．

を除く $SUBG_{u}$ 中の全ての節点を.

$\omega(\{v_{|F_{J}XT_{u}|-t},v_{|F_{J}XT_{u}|}\}\cup SUBG_{T\Lambda}IL‘)=$$|C_{\dot{*}}|+2>\omega(\{u\}\cup SUBG_{u})$である．

が [2] を満たす場合．$SUBG\tau Arr_{J}$ は$\acute$$\omega(\{u\}\cup SUBG_{u})\leq\omega(\{v_{|F_{J}XT_{u}|-1,}.v_{|F_{J}XT_{u}|}\}\cup$$SUBG_{T\Lambda;r_{J}}))$$r$$C_{i}\subseteq SUBG_{\Gamma\Lambda t\Gamma_{J}}r$とする．このとき以下が成立する．
$(v_{|F_{J}XT_{u}|-1}, v_{|EXT_{u}|})\in E$

は

含むから，

$EXT_{u}[|EXT_{u}|]\})$

はのうち少なくとも 1 個に含まれ。

SUB $G,,$ $=\Gamma(v_{i})\cap(SUBG-\{u,v_{1,}.v_{2}, , ..,v_{i-1}\})$$=$$|C_{k}|$$C_{k}$$\ldots,$$[2]C_{1},C_{2_{\dot{\prime}}}\ldots,$$|-1,v|F_{J}XT$。$|\}$

$r$

$=$

.

$C_{1}-\{r\},C_{2}-\{r\},$ $\ldots,C_{k}-\{r\}$なるサイズ $\omega(SUBG_{u})-1$ のクリークを含む．い
ま $SUBG\prime r\Lambda;r_{J}(\subseteq SUBG_{u})$ は$SUBG_{7\Lambda}rr_{J}$$r$を除く $SUBG_{u}$ 中$=\Gamma(\{v_{|F_{J}XT_{u}|-1},v_{|F,XT_{u}|}\})\wedge$の全ての節点に隣接するのであるから，これらのク$\cap(SUBG-\{u,v_{1},v_{2}, \ldots,v_{|F_{J}XT_{u}|-2}\})$

リーク中の節点は全て $v_{|F,XT_{u}|-1}$ および$v_{|F_{J}X}$

川に隣接する．従って
ハ$=$$(\{v_{|F_{J}XT}$$\omega(\{v_{|F,XT_{u}|-1},v_{|F_{J}XT_{u}|}\}\cup SUBG_{TA}rr_{l})=C_{2}-1+$$|-1,v_{|F_{J}XT_{u}|}\})$。

$\cap(\{v_{|F_{J}XT_{u}|-1,}.v_{|F_{J}XT_{u}|}\}\cup SUBG_{u})$$2=\omega(\{u\}\cup SUBG_{u})$$=\Gamma(\{v_{|F,XT_{u}|-1},v_{|F_{J}XT_{u}|}\})\wedge$

であり，この場合も題意は成立する．口$\cap SUBG_{u}$$\subseteq SUBG_{A}$

補題 5 を利用して，アルゴリズムに以下の限定操.

作を導入する．

また，$|SUBG_{T\Lambda t\Gamma_{J}}|=\Delta-k-1$

である．したがって，$SUBG\tau\Lambda rr_{r}(\subseteq SUBG_{u})$に含(a) $|SUBG_{T\Lambda rr_{l}}|=|SUBG_{u}|-1$ の場合:,
中に $SUBG_{u}$ 中の最大クリーク
常に$SUBG_{\Gamma A,\Gamma_{J}}$173
以上のサイズのものが存在する．そこでこの場合
SUBG,, に対する探索を省略するために．SUBG,, $:=$$\acute$$\emptyset$と設定する．
$(b)SUBG_{T\Lambda}$

いま，既に得られている最大クリークを Qmaxとすると，探索のある時点において EXPAND が行う処理の手数は，その時点で極大クリークが得ら$\subseteq$

$V$

$()$

lL $\leq|SUBG_{q},.|-2$ の場合:

この場合は SUBG,,. と行う．

$SUBG\prime r\Lambda t\Gamma_{l}$れているかどうかによって変る．そこで，以下の場
両方に探索を 合分けを行う．
$(i)SUBG\neq\emptyset$の場合以上の操作全体を合わせて．，改めて拡張した意味に
このとき，EXPAND はまず最大次数節点
おいて “部分問題の統合による探索領域削減’ と呼ぶ． 選出，集合 SUBG,, と $EXT_{2l}$ の定義，および
$()$

$u$

の

$\acute$$EXT_{\tau},$.

アルゴリズム上でこの処理を実現するために，図 の最後尾 2 節点を用いて集合の定義を
2 の探索領域削減部分 1301-1308 行を 1300-1400 行 行う．
間に，2401-2403 行を 2400-2500 行間にそれぞれ挿入
以下，各 $SUBG\subseteq V$ において SUBG 中の節点の$SUBG_{TA\Gamma\Gamma,}$

する．

隣接関係は．
，次のように隣接リストを用いて与えるも
以上，図 1,2 を合わせて得られるアルゴリズム全 のとする．即ち，各探索深さにおいてサイズ $|SUBG|$
体を，本稿の改良アルゴリズム $MCP_{1}’$ とする．の 1 次元配列を用意し，これを SUBG の節点を表現する普遍集合とする．この各節点 $v\in SUBG$ の隣接
4 最大時間計算量評価
節点集合を抽出して，SUBG 中の各節点の隣
節点数 のグラフ $G=(V, E)(|V|=n)$ に対する 接リストを生成する．
EXPAND(V) の最大時間計算量を $T(n)$ とする．ここ
このとき各節点に対する隣接節点のリストの長さ$SUBG\subseteq V$ に対する EXPAND (SUBG)
で，任意のは高々 $|SUBG_{u}|+1$ であることから上記処理に要すの最大時間計算量 $T(|SUBG|)$ について，次の関係式 る手数は $O(|SUBG|\cdot(|SUBG_{u}|+1))$ である．これ$\Gamma(v)$$n$が成り立っ．

より，そのような上界 $C_{1}|SUBG|\cdot(|SUBG_{2l}|+1)$$T(|SUBG|)$

を与える定数を$C_{1}$とする．

$\leq T(|SUBG_{u}|)+\sum_{i}^{1}\mathscr{T}_{1}^{XT_{u}|-2}T(|SUBG_{v_{i}}|)$$+T(|SUBG_{T\Lambda\Gamma\Gamma_{l}}|)$$EXT_{ll}=SUBG-\{u\}-SUBG_{u}$ を生成する操$+C|SUBG|\cdot(|SUBG_{\tau},.|+1)$

ここで， は
$u$

$S$

. (1)

む r $BG$ において最初に選択する最大次数節点とする．また，$S$集合

乙 BG ’ $=\Gamma(u)\cap S$ 乙 rBG.

$SUBG\prime r\Lambda$$\acute$. $=S$ 乙$BG-\{u\}-SUBG.$,$EXT_{\tau r}$

$|\}$

丁。

とする．

$\hat{\Gamma}(\{EXT_{\tau r}[|EXT_{8l}|-$. であることを考慮すれば，集合の定義は $O((|SUBG_{2J}.|+1)^{2})$,$\leq$$O(|SUBG|\cdot(|SUBG_{u}|+1))$ の手数で可能である．

$SL^{r}BG_{\tau_{i}},=\Gamma(v_{2})\cap((EXT_{lA}-\{v_{1}, v_{2,}.\ldots, v_{i-1}\})\cup$

SUBG,,),
および，

ここで上界 $C_{3}|SUBG|\cdot(|SUBG_{u}|+1)$ を与える定数を$C_{3}$

もし$SUBG_{T\Lambda J\prime}=\Gamma\wedge(\{EXT_{\tau},.[|EXT_{1l}|-1]$$C_{2}$

fr. について，$1|,$ $EXT_{2l}[|EXT_{ll}|]\}\subseteq SUBG_{\tau t}$$\not\in$$=\{v_{1:}v_{2}, \ldots,v_{|F_{J}X}$

作は $O(|SUBG_{1l}|+1)$ の手数で可能である．そこで
上界 $C_{2}(|SUBG_{u}|+1)$ を与える定数を,$EXT_{\tau},.[|EXT_{\tau},.|]\})$$\cap(SUBG-\{u,v_{1},v_{2}, \ldots,v_{|F_{J}XT_{u}|-2}\})$とそれぞれおく．

とする．
$SUBG\tau\Lambda \mathfrak{l}\Gamma_{l}$$=$EXPAND は $SUBG_{u}$$|SUBG_{u}|-1$ であれば，$:=$$\emptyset$

とする

この操

作は $O(|SUBG_{l1}|+1)$ で行うことができるので，$C_{4}(|SUBG_{u}|+1)$ を与える定数を$(ii)SUBG=\emptyset$$C_{4}$とする．

の場合

この式末尾の $C|SUBG|\cdot(|SUBG_{u}|+1)$ は，この$SUBG_{u}=SUBG_{\eta\prime i}=\emptyset$ であるから，このとき，ような問題分割に必要な全ての処理に要する多項式 アルゴリズムはこれらの空集合性の判定を行った後，オーダの計算量の上界であり 定数 $C>0$ は以下の様に定義する．ただしここでは，グラフの表現 (データ構造) に隣接リストを採用する．
$j$

極大クリークを決定する．また，得られた極大クリー
クのサイズが既に得られた最大クリークのサイズより大であれば．，最大クリークのサイズ $|Q \max|$ の更
新を行う．

174
極大クリークのサイズにっいては，各深さにおい が $|SUBG_{tl^{l}}|=|SUBG_{u}|+1$ となる SUBG について節点が選出されるごとにクリークサイズの変数を て要する計算量を考える．
$SUBG_{u’}$ 中の最大次数節点
この仮定のもとで，$|ROOT|$ 分だけ加算，バックトラック時には減算すればよい．即ちクリークサイズは 1 語だけで格納可 の次数は高々 $|SUBG_{u}|$ である．そこで，節点$u_{1}$$u_{1}$の隣接節点集合 $SUBG_{u_{1}}$ のサイズを $|SUBG_{u_{1}}|=$

能である．

このように格納した 2 つのクリークサイズの比較

は定数オーダーで可能であるから，クリークサイズの$|SUBG_{u}|-k(0\leq k\leq|SUBG_{u}|)$と表す．このとき，式 (1) より，$T(|SUBG_{l^{f}}|)=T(|SUBG_{u}|+1)$

で上界を与えることができる．
更新は適当な定数以上から: 式 (1) における定数 $C$ を$C_{5}$$\leq T(|SUBG_{u}|-k)$$+ \sum_{arrow-\iota}^{|.F_{J}XT_{u^{f}}|-2}T(|SUBG_{v_{*}}.|)$$C= \max\{C_{1}, C_{2},C_{3}., C_{4}, C_{5}\}$によって定義する．

$+T(|SUBG_{TA}rr_{l}|)$

また，EXPAND の計算量 $T()$ は，その性質上対象とする節点集合のサイズに関して単調である．

$+C(|SUBG_{u’}|+1)\cdot(|SUBG_{u_{\rceil}}|+1)$

$()$

節点

ら，

$u_{1}$

は $SUBG_{2l’}$ 中で最大次数の節点であるか$SUBG_{\tau l’}$主要定理証明に先立ち，先ず，EXPAND

$()$

による

$u_{1}$.

における$v_{1}.,v_{2},$$\ldots,$$v_{|F_{J}XT_{u},|-2}$の次数は$|SUBG_{\tau_{i}},|(1\leq i\leq$の次数以下である．従って，各子問題の時間計算量評価結果を以下に与える．
I $EXT_{u’}|-2)$ は $|SUBG_{\tau\iota}|-k$ 以下である．ただし，[補題 6] 節点集合が SUBG で，最大次数節点 の $|’|SUBG_{u}|-1$ の場合は SUBG,$l:=$
次数が $|SUBG_{u}|\geq 0$ なる任意のグラフにおいて， と代入を行う．このときは上記多項式項の定義に$u$$\emptyset$$T(|SUB_{u}|)\leq C|SUBG_{u}|^{2}$ としてよい．
EXPAND $(SUBG_{u})$ , EXPAND $(SUBG_{n_{i}})$ , および より，$[1||EXT_{u}’|\geq 2$ である場合:$C’=$
EXPAND $(SUBG_{TArr_{l}})$ の最大時間計算量は，$(a)|SUBG_{T\Lambda};r_{J}|\leq|SUBG_{u}|-2$ の場合; $T()$ のとすると，それぞれ，$T(|SUBG_{u}|)\leq C’2^{0.369894|SUBG_{u1}}(|SUBG_{u}|+1)^{2}$ ,単調性により，$10^{6}\cdot 2C$$T(|SLBG_{\tau_{i}},|)\leq C’2^{0.369894|SUBG_{v}|}i(|SUBG_{2_{*}},.|+1)^{2}$$(1\leq i\leq|EXT_{l}|-2)$ ,$T(|SUBG_{\tau\ell}|+1)$$\leq((|SUBG_{2l}|+1)-(|SUBG_{u}|-k)-\mathfrak{Y}$$T(|SUBG_{u}|-k)$

および，$+T(|SUBG_{TAi\Gamma_{l}}|)$$T(|SLBG_{T\Lambda\Gamma\Gamma,}|)\leq C’2^{0.?69894|SUBG_{TA}tr,|}$.
(証明)$(|SUBG_{TA\prime\prime},|+1)^{2}$.

$+C(|SUBG_{l}|+1)\cdot(|SUBG_{u_{1}}|+1)$

以下，最初に $T(|SUBG_{1A}|)$ について，補題の関係の成立を示す．証明は最大次数 $|SUBG_{u}|$ に関する数学的帰納法による．
$|SUBG_{l}|$先ず，$\emptyset.,$

$0$

$=$

ここで，帰納法の仮定により，$T(|SUBG_{\tau A}|+1)$の場合，である．ここ$SUBG_{u}$$=$$\leq(k-1)\cdot C’2^{0.369894(|9tJt?G_{u}\}-k)}$$((|SUBG_{2A}|-k)+1)^{2}$$SUBG_{\tau;_{i}}=\emptyset(1\leq i\leq|EXT_{1l}|)$で節点.

$u_{1}$

を $G$ の SUBG,, による誘導部分グラフ中の最大次数節点とすれば．定数$\acute$$C$$+T(|SUBG_{TAJ\Gamma,}|)$の定義により，$T(|SUBG_{u}|)\leq C|SUBG_{2l}|\cdot(|SUBG_{u_{1}}|+1)$$+C(|SUBG_{u}|+1)\cdot(|SUBG_{u_{1}}|+1)$$<C’2^{0}\cdot(_{2}\ovalbox{\tt\small REJECT})$$<C’\cdot 1\cdot(|SUBG_{u}|+1)\cdot(|SUBG_{u\tau}|+1)$$=C’\cdot 2^{0.369894\cdot 0}\cdot(|SUBG_{u}|+1)^{2}$.

従って，題意は成立する．
この場合， ( 乙 BGrli ), $T(|SUBG_{T\Lambda}tr_{l}|)$ につい
$T$

$|S$

$|$

ても同様に題意は成立する．
次に，ある $|SUBG_{u}|\geq 0$ 以下の全ての $|SUBG_{u}|$において補題中の全不等式が成立すると仮定する．この仮定のもとで．SUBG 中の最大次数節点 $u’$ の次数$\acute$$(|$

SUBG,. $|+2)^{2}$$+T(|SUBG_{TA\Upsilon\Gamma_{l}}|)+C(|SUBG_{u}|+2)^{2}$$|SUBG_{T\Lambda\Gamma\Gamma},|=((|SUBG_{\tau\iota}|-k)-2$.
V ま，$\backslash$て，$T(|SUBG_{u}|+1)$$\leq C^{l}2^{0.369894(|9UBG_{u}|)k-1}(_{2}\ovalbox{\tt\small REJECT})$$(|SUBG_{u}|+2)^{2}$$\text{従^{}\prime}$

.

っ

175
$+C’2^{0.369894(|SUBG}$ 。$|-k-2)(((|SUBG_{\eta},.|$$+C(|SUBG_{u}|+1)\cdot|SUBG_{u_{\rceil}}|$$-$$k)-2)+1)^{2}+2C(|SUBG_{u}|+2)^{2}$$\leq C^{l}2^{0.369894|8UBG_{u}|}(|SUBG_{u}|+1)^{2}$$+C(|SUBG_{2A}|+2)^{2}$$\leq C’2^{0.369894(|8UBG_{u}|)}(\frac{k-(1-\ovalbox{\tt\small REJECT}_{2}^{\rceil})}{2^{0.B69894k}}$$+10^{-6})(|SUBG_{u}|+2)^{2}$$\leq C’2^{0.369894|SUFtG_{u}|}(1+\frac{1}{10^{6}\cdot 2^{O.fl69894|STJlG_{\text{。}}|}})$$k\geq 0$ において
ここで，文献 [4] と同様にして，$\frac{k-(1-\ovalbox{\tt\small REJECT}_{2}^{1})}{2}<1.29225$$(|SUBG_{u}|+2)^{2}$$\leq C’2^{0.369894(|SUBG}$ $|+\iota)((|SUBG_{u}|+1)+1)^{2}$

であることを証明できる。

(付録，[補題 Al]). 従って，であり，やはり題意は成立する．

以上，帰納法による帰結により． 任意のにおいて，EXPAND $(SUBG_{u})$I$T(|SUBG_{u}|+1)$$\acute$$C’2^{0.369894|SUBG_{u}|}$$\leq$$($

1.29225.

$10^{-6})$$+$$|SUBG_{u}$$=C’2^{0.369894|_{\iota}9\Gamma JBG_{u}|}$. 1.292251. $(|SUBG_{u}|+2)^{2}$$<C^{l}2^{0.369894|SUBG_{u}|}\cdot 2^{0.369894}\cdot(|SUBG_{u}|+2)^{2}$$=C^{l}2^{0.369894(|SUBG_{u}|+1)}((|SUBG_{u}|+1)+1)^{2}$$(b)|SUBG_{T\Lambda\Gamma\Gamma_{r}}|=|SUBG_{u}|-1$

EXPAND $(SUBG_{vi})$
EXPAND
$||$

.

お

よ

び

についても，全く同様にして題意の成立を示すことができる．
以上より，帰納法帰結として，補題が証明された．
$(SUBG_{T\Lambda rr_{l}})$

口

の場合;

と設定しているから

これより，次が成立する．
[補題 7] 節点数 , 最大次数 $\Delta\geq 0$ なるグラフにおいて定数 $C”$ を $C”=1.2\cdot 10^{11}$ とする．このとき$T(|SUBG_{u}|+1)$$\leq((|SUBG_{\tau r}|+1)-(|SUBG_{IJ}|-k)-2-1)$$n$$T(|SUBG_{u}|-k)$.

EXPAND(SUBG) の最大時間計算量 $T(n)=T(|V|)$$+C(|SUBG_{\tau r}|+1)^{2}$

十丁 $(|S$ び $BG_{T\Lambda\Gamma\Gamma_{r}}|)+C(|SUBG_{kJ}.|+1)^{2}$.

は次を満たす．
$|$$T(|V|)=T(n)\leq C’C’’2^{0.3827\Delta}n+Cn\cdot(\Delta+1)$

従って，

.

(証明) 式 (1) より，$T(|SUBG_{\tau},.|+1)$$i$$T(n) \leq T(|SUBG_{u}|)+\sum_{i=1}^{|F_{J}XT_{u}|-2}T(|SUBG_{\tau_{i}},|)$$\leq(k-2)T(|SUBG|-k)$$+T(|SUBG_{T\Lambda\Gamma\Gamma_{z}}|)+2C(|SUBG_{u}|+1)^{2}$
$|S$

$0$

についての題意の関係が成立する．

$(|SUBG_{u}|+2)^{2}$$SUBG_{u}=\emptyset$$\geq$.

$+T(|SUBG_{T\Lambda J\Gamma,}|)+Cn\cdot(\Delta+1)$である．ここで [補題 6] を用いればび $BG_{T\Lambda\prime\prime},|=|S$ ひ $BG_{?A}|-1$ であるから．

$T(n)\leq(n-A--1)C$ ‘ $2^{0.369894\Delta}(\Delta+1)^{2}+Cn$ .

$\acute$$T(|S$ 乙 rBG?、$|+1)$$(\Delta+1)$$\leq(k-2)\cdot C’2^{0.369894(|SUBG_{u}\vdash k)}$$1$$\leq nC’2^{0.369894\Delta}(\Delta+1)^{2}+Cn\cdot(\Delta+1)$$((|SUBG_{2},.|-k)+1)^{2}$

定数$+C^{l}2^{0.369S94(|SUBG_{u}|-k-1)}$$C”$の設定により，任意の$(\Delta+1)^{2}<C’’2^{0.000006\Delta}$$+(C+1)(|SUBG_{u}|+2)^{2}$$1$$A2])$$=C’2^{0.369894(|9UBG_{u}|)}( \frac{k-(2-\urcorner_{2}\ulcorner m^{1}\S\pi)}{2^{t1.Y69894k}}$$\Delta$.

においてが成立する (付録，[補題から，$T(n)<nC^{f}C^{ll}2^{0.369894\Delta}\cdot 2^{0.000006\Delta}+Cn\cdot(\Delta+1)$$+10^{-6})(|SUBG_{rr}.|+2)^{2}$$=C’C”2^{0.3699\Delta}n+Cn\cdot(\triangle+1)$ 口$=C’2^{0.369894(|SUBG_{u}|)}( \frac{k-(1+(1_{\urcorner_{2}\cap^{1}m89T}-))}{2^{0.\hslash 69894k}}$$+10^{-6})(|SUBG_{u}|+2)^{2}$$<C’2^{0.369894(|SUBG_{u}|)}( \frac{k-(1-\ovalbox{\tt\small REJECT}_{2}^{1})}{2^{0.369894k}}$$+10^{-6})(|SUBG_{u}|+2)^{2}$

よって上記と同様に成立する．
$[2]|EXT_{\eta^{l}},|\leq 1$ である場合:$u’$の子節点のうち探索されるのは高々.

以上から，本論文の結論となる次の定理を得る．
[定理] 節点数 のグラフにおいて，グラフの最大次
$n$

$|$

数

$\Delta$が0:定数):を満すならば．最大クリーク問題は $O(n^{1+d})$ 時間で決可能である．
$\Delta\leq 2.704dlgn$$u_{1}$のみであ(d$\geq$$\acute$$1$る．従ってこの場合，(証明) 補題 7 において $\Delta\leq 2.704dlgn$ とすれば
$1$

$T(|SUBG,,|+1)\leq T(|SUBG_{u_{\rceil}}|)$

176$T(n)$$\leq$$n$. $C’C^{ll}2^{0.3699\cdot 2.704dlgn}n+Cn$ .

$(2.704dlgn+1)$[2] I. M. $BoIne.$ , M. Budinich, P. M. Pardalos, and M.
$uThe$ maximum clique probleJn,“ in: D.$PeMo\dot,$
Z. Du and P. M. Pardalos (Eds.). Handbook of
Combinatorial Opt.$\dot{u}ni.ation,$ Supplexne.nt vol.A,
KluweJ Academic Pubkshers: pp.1-74, 1999.

$\leq nC’C’’n^{d}+2.704Cn\cdot lgn^{d}+Cn$$\leq C’C’’n^{1+d}+2.704Cn^{1+d}+Cn^{1+d}$$=(C’C”+3.704C)n^{1+d}$

5.

Completeness, W. H. Freeman and Company: New
York, NY, USA, 1979.

口

むすび
本稿では，文献 [7] の更なる改良結果として，節点数 のグラフにおいて最大次数 $\Delta\leq 2.704dlgn(d\geq$0:定数) であるならば，最大クリーク問題は $O(n^{1+d})$なる多項式時間で解決可能であることを示した．この結果は，最大クリーク抽出の基本アルゴリズム [4]中に “部分問題の統合による探索領域削減’ という手
$n$$\acute$法を導入し，解析を更に詳細化した上でアルゴリズ
ムを改良することにより達成している．ここでの結果は，アルゴリズム，解析の双方において，文献 [4]の単純さをほぼ保っている．アルゴリズムの単純さは，文献 [9] と同様，実用上の高速性にもつながるものである．

[3] M. GroeteJ, L. Lovigz, and A. Sehrijver, $uPoly-$
nomial algorithm for pprfect graphs.“ Annals of
Digcrete Math., vol.21, pp.325-356, 1984.
[4] 中西裕陽，富田悦次． 最大クリーク問題の多項式時間的可解性のー結果，” 信学論 (D), vol J93-D, no.4,
pp.417-425, Apr. 2010.
$u$$\acute$[5] 松野浩嗣，田中都子，定数次数のグラフの最大クリー
クを抽出するビット演算アルゴリズム，” 情処学論，$vo1.37$ , pp,1869-1872, 1996.
$u$[6] E. Tomita, A. Tanaka and H. Tahhashi: $uThe$for generating all maxworst-case time”
imal tliques and computational
Theoretical Computer Science, vol.363., pp.28-42,$t^{\backslash },omp1\dot{m}ty$$\alpha peximent_{\iota}s,$

2006.
[7] 中西裕陽富田悦次． 最大クリーク問題の多項式時間的可解性の改良結果:” 信学技報: COMP2010-43,$pp.29-36_{i}D\epsilon c.$ .2010 (信学論 (D) 採録決定).
$u$

本稿の結果は，最大クリーク問題を容易に (多項式時間的に) 解ける範囲を従来よりも一層拡張できたことを示した．特に，グラフの次数に関する前提$d\geq 1$ から $d\geq 0$における定数 に対する条件を，へと拡張したことにより，グラフが疎で が 1 よりも小さくなるに従い，所用計算時間オーダは節点数の 2 乗よりも小さくなる．この結果は，多くの応
$d$

$d$

$n$

用例 ([2], [10], [11], 他) との関係においても重要である．

今後の課題は，アルゴリズムと解析双方の単純性を出来る限り保ちながら，最大クリーク問題の定量的
時間計算量に関する結果を更に改良することである．

$\acute$[8] C. Bron and J. Kerbosch, $uAlgorithm457_{:}$ Finding allof an undirected graph,” Commun.
ACM. vol.16, pp.575-577, 1973.
$cJique_{\wedge}s$[9] 新道美喜男，富田悦次．“最大クリークを抽出する単純なアルゴリズムとその最大時間計算量$ ” 信学諭(D): vol. $J71-D,\cdot$ pp.472-481, March 1988.
$\acute$[10] E. Tomita, Y. Sutani, T. Higa.shi, S. Takahashi
and ffist.eJ branchand M. Wakatsuki,
and-bound algorithm for flnding a maximum
clique,“ WALCOM 2010, LNCS 5942, pp.191-203,$uA\dot{\alpha}mple$

2010.

謝辞文献 [7] の内容に関して貴重なご意見をいた [11] E. Tomita, T. Akutsu, and T. Matsunaga,“Efficient algorithms for finding maximum and
だいた，電通大・垂井淳准教授をはじめ電子情報通:tools for bioinfcrmaximal
信学会コンピュテーション研究会各位に深謝します．
matics,” in “Biomedical Engineering, Trends in
El ronics., Communications and Software,
また，ご支援協力をいただいた電通大先進アル
Anthony N. Lagkovski (Ed.), ISBN: 978-953-307ゴリズム研究ステーション高橋治久教授，北大原
475-7, $InTecA$ , pp.625-640, 2011. Available from:
口誠教授，他関係者に感謝します．なお．本研究はhttp: $//www.intechopen.(^{\backslash }.om/articJ\epsilon_{\wedge}s/show/title/$
efficient-algorithms-for-finding-maximum-andによる
科研費基盤 (B), (C), および総務省 SCOPE$cJiqu\epsilon_{\wedge}s$$E\#\epsilon c:tive$$\propto t$$\acute$研究助成を受けている．

参考文献[1] M.R. Garey and D.S. .Iohnson, Computers andIntaractability: A Guide to the Theory of NP-$maxima1-cJique_{\wedge}+$effective-tools-for-bioinfomatioe