数理解析研究所講究録992 巻 1997 年 12-19

12最大共通誘導部分グラフ問題の MAX SNP-hardness について*

九州大学大学院システム情報科学研究科情報理学専攻{sugino,
1

正代隆義*

. 孔–*

$\text{杉野}$$\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{u}\mathrm{d}\mathrm{a}\mathrm{i}$}$\copyright \mathrm{i}.\mathrm{k}\mathrm{y}\mathrm{u}\mathrm{s}\mathrm{h}\mathrm{u}-\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{j}\mathrm{p}$はじめに最大共通誘導部分グラフ問題とは, 入力として 2 つのグラフが与えられたときに, 最大で共通な頂点から誘導される部分グラフを求める問題である. 2 つのグラフの頂点数と辺の数が等しいとき, それらのグラフから最大共通誘導部分グラフを取り除いた残りのグラフの頂点数を, 入力の 2 つのグラフの距離と考えることができる. グラフ理論において, グラフの距離はいくつか定義され, それらの関係について研究されている [5].

また, あるグラフの変換操作を固定し, -方のグラフから他方のグラフヘ変換するその操作の回数を距離と定義したとき, その距離を計算する問題に対して計算量理論的な研究もなされている [1,4]. V.

$\mathrm{K}\mathrm{a}\mathrm{n}\mathrm{n}[3]$は, グラフの類似性を判定する最大共通誘導部分グラフ問題が,MAX SNP-hard であることを示した. このことはすなわち, この問題が任意の $\epsilon>0$ に対して最適解の相対誤差$\epsilon$の近似アルゴリズムを持ちそうにないことを示している. V. Kann はさらに入力とするグラフの次数が定数で制限されMAX SNP-hard であることを示した [3]. しかし, その次数を制限している定数は 25 というかなり大きなものである. この論文では, 同じ数の頂点と辺を持つ 2 つのグラフの類似性の判定に着目し, 2 つのグラフの次数が 3 でおさえられているときでも最大共通誘導部分グラフ問題は MAX SNPhard であることを示した. また 2 つのグラフがともに連結で次数が 3 でおさえられているときも, MAXSNP-hard であることを示した. 我々は, MAX SNP-hard であることを示すにあたって MAX SNP 完全として知られている最大 3 次元マッチング問題から 還元を行う. -方, この最大共通誘導部分グラフ問題は完全であることも知られている. さらに本論文ではこの問題について, 与えられる 2 つのグラフの次数が制限され, かつ頂点数と辺の数が等しい特殊な場合についての完全性について議論する.ているときも,$L$$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$2

最大共通部分グラフ問題$G=(V, E)$ を無向グラフとする.

する辺が$E’$に存在する} とする.

分グラフという. また,とする.

た,

このとき,

$V$

$G_{1}$と$V_{1}’\subseteq V_{1}$と$G_{2}$$G|_{E’}=(V|_{E}’, E’)$の部分集合 $V’$ に対して,$G|_{V’}=(V’, E|_{V}’)$

部分グラフであるとは,の部分集合 $E’$ が与えられたとき,

このとき,$G_{1}=(V_{1}, E_{1}),$ $G_{2}=(V_{2}, E_{2})$う. 頂点数最大の$E$$E|_{V’}=${$V..|_{E’}=\{.v\in V|v$

を端点とを $E’$ の辺誘導部分グラフ, 略して, 部$\{u,$$v\}\in E|u,$$v$

は $V’$ に含まれる頂点}

を $V’$ の頂点誘導部分グラフ, 略して, 誘導部分グラフという.

を無向グラフとする. 無向グラフ $G=(V, E)$ が$V_{2}^{1}\subseteq V_{2}$が存在しの共通誘導部分グラフを$G_{1}$$G_{1}|_{V_{1}^{l}}$と$G_{2}$と$G_{2}|_{V_{2}’}$$G_{1},$$G_{2}$

まの共通誘導が共に $G$ に同型であるときをいの最大共通誘導部分グラフという. 本論文

では, 次のような問題を考える.

定義 1.

次数制限最大共通誘導部分

SUBGRAPH (MAX CIS-B)$\sigma_{\text{フ}^{}\backslash -}$フ問題 (MAXIMUM BOUNDED COMMON INDUCED$)$

入力: 無向グラフ $G_{1}=(V_{1}, E_{1}),$ $G_{2}=(V_{2}, E_{2})$ .

ただし,$G_{1},$ $G_{2}$の次数はともに高々定数 $B\geq 0$ である.

13
問題:

$G_{1},$$G_{2}$の最大共通誘導部分グラフを求めよ.

定理 1. (V. Kann [3]) MAX CIS-B は $B\geq 25$ のとき MAX SNP-hard である.

MAX CIS-B の入力として与えられる 2 つのグラフがともに連結であるとき, 次数制限連結最大共通誘導部分グラフ問題 (MAXIMUM CONNECTED BOUNDED COMMON INDUCED SUBGRAPH (MAX CIS-CB) と呼ぶ.
$)$

3最大共通部分グラフ問題への$L$還元

この章では, 入力される 2 つのグラフの頂点の次数が高々 3 のときに, 次数制限最大共通誘導部分グラフ問題が MAX SNP-hard であることを示す.

定義 2.
する.

$\Pi_{1}$$\Pi_{1}$と垣 2 を 2 つの最適化問題とする.の任意の入力をして以下のような正定数とし, 入力$I$$\alpha,\beta$

$I$

$f$

:

$\Pi_{1}arrow\Pi_{2}$を, 多項式時間計算可能であるような関数との最適解のコストを OPT $(I)$ とする.

が存在するとき,$f$\iota よ$L$$\Pi_{1}$の任意の入力$I$に対還元であると呼ぶ.

1. $oPT(f(I))\leq\alpha OP\tau(I)$ .
2. 値
$I$

$c_{2}$をもつ $f(I)$ のすべての解に対して,$|OPT(I)-C_{1}|\leq\beta|OPT(f(I))-c2|$ となる値 cl をもつの解を多項式時間で見つけることができる.

本章では, 次の問題から次数制限最大共通誘導部分グラフ問題への$L$還元を考える.

最大 3 次元マッチング問題 (MAXIMUM BOUNDED THREE DIMENSIONAL MATCH-ING (MAX 3DM-B)$)$

入力: $X\cross Y\cross Z$ の部分集合 $M$ .

ただし,

$X$

,$\mathrm{Y}$,$Z$

は互いに交わりのない 3 つの集合である.

これらの集合の要素を,$X$$\{x_{1,2,3}xx, \cdots, x_{p}\}$$=$$\{y1, y_{2},y3, \cdots,yp\}$

,

$Z$

$=$

$\{z_{1,2,3}zz, \cdots, z_{p}\}$

,

$M$

$=$

$\{m_{1}, m_{2},m_{3}, \cdots,m_{q}\}$$\mathrm{Y}$.

,$=$とする.

また,$M$の中の $X$ ,$Y$,$Z$の各々の要素の出現回数は, 最大 $B\geq 0$ 回であるとする.

問題: 最大マッチングを求めよ. ただし, マッチングとは,$X,$ $Y,$$Z$のどの要素も高々 1 度しかあらわれないような $M$ の部分集合である.
我々は,MAX 3DM-B の入力$X_{M}$$=$$\mathrm{Y}_{M}$$=$$Z_{M}$$=$

に対して,$\mathrm{M}${ $x\in X|(x,${ $y\in Y|(x,${ $z\in Z|(x,$$y,$$y,$$y,$$z)\in M$ となるような$y\in \mathrm{Y}$と z\in Z が存在する},z\in Z が存在する},$z)\in M$ となるような $x\in X$ とが存在する}$z)\in M$ となるような $x\in X$ と$y\in \mathrm{Y}$14とするとき,と仮定する. すなわち,$X_{M}$$=$$\{x_{1}, x_{2,3,|x|}x\cdot, .

$Y_{M}$$=$$\{y_{1}, y_{2},y3, \cdots, y_{|Y_{M}|}\}$$Z_{M}$$=$$\{_{Z_{1,2}}z, Z_{3,|z|}\ldots, Z\}M$, X\}M$’,の要素で実際に $M$ に出現するのは, インデックスの小さい方からそれぞれ $|X_{M}|,$ $|Y_{M}|,$ $|Z_{M}|$ 番目までである. また, このとき,$X$,$\mathrm{Y}$,$Z$$p$$=$$|X_{M}|$$|Y_{M}|$$\geq$$|Z_{M}|$$\geq$と仮定する. このように仮定しても –般性を失わない.
定理 2. (V. Kann [2]) MAX 3DM-B は $B\geq 3$ のとき MAX SNP 完全である.
定理 3. MAX CIS-B は $B\geq 3$ のとき MAX SNP-hard である.

MAX 3DM-B からの証明.

MAX 3DM-B の入力 $M$ の中の $X$ ,, $Z$ の各々の要素の出現回数は高々 3 回とする. 一般に問題の入力を で表す. MAX 3DM-B の場合, 入力$L$還元を示す. ただし,

$Y$$I$は $M\subseteq X\cross Y\cross Z$ のことである.

ただし,$M$は $P\leq q$$I$を考えれば十分であり, かつ $q\leq 3p$ である.

MAX 3DM-B の任意の入力から MAX CIS-B のそれに対応する入力 \sim 還元する多項式時間アルゴリズム
をとし, 3 つの頂点からなる完全グラフをと表すことにする. MAX CIS-B の–方のグラフである$f$$K_{3}$$G_{1}=(V_{1}, E_{1})$る.の構成法を以下に示す. 添字 $i(1\leq i\leq|Z_{M}|)$ に対して, 図 1 に示すように $G[i]$ をつく

G[i] は,,$V[i]$$=$$\{v_{j}^{k}[i]|1\leq j\leq 3,1\leq k\leq 3\}\cup\{a[i]\}-$$E[i]$$=$$\{\{v_{j}^{1}[i], v^{2}j[i]\}, \{v_{j}^{2}[i], v^{3}j[i]\}, \{v_{j}^{31}[i], vj[i]\}|1\leq j\leq 3\}$$\cup\{\{a1^{i}], vj[1]i\}|1\leq j\leq 3\}$からなる (図 1 参照).

図 1: $G[i]$このとき,$G_{1}=(V_{1}, E_{1})$は以下のように表される.

$V_{1}=|Zi=1\cup V[i]M|$.

$E_{1}.=|Z_{M,\cup^{1}E[i]}$

.

$i=1$

以上が$G_{1}$の構成法である (図 2 参照).

15

図 2: MAX$3\mathrm{D}\mathrm{M}$のある人力に対応するグラフ$G_{1}$16
つぎに,$G_{2}=(V_{2}, E_{2})$$G_{x}[i](1\leq i\leq|X_{M}|)$の構或法を示す.

をつくる.

$G_{x}[i]$の$X_{M}$

$i$

番目の要素

$x_{i}$を表すために, 図 3 に示すように,は,,$V_{x}[i]$$=$$\{u_{x}^{k}[i]|1\leq k\leq 3\}$$E_{x}[i]$$=$$\{\{u_{x}^{1}[i],u^{2}[xi]\}, \{u_{x}^{2}[i], u^{3}[xi]\}, \{u_{x}^{31}[i],ux[i]\}\}$からなる (図 3 参照).

$\mathrm{u}_{\mathrm{x}}^{\sim}[_{1}\rfloor$$\mathrm{u}_{\mathrm{x}}^{\mathrm{J}}[11$

図 3: $G_{x}[i]$$Y_{M},$$Z_{M}$からなる.

についても同様に, それぞれ $G_{y}[i],$$G_{z}[i]$$G_{z}[i]$をつくる.

$G_{y}[i]$は,,$V_{y}[i]$$=$$\{u_{y}^{k}[i]|1\leq k\leq 3\}$$E_{y}[i]$$=$$\{\{u_{y}^{1}[i], u^{2}[yi]\}, \{u_{y}^{23}[i], u_{y}[i]\}, \{u_{y}^{3}[i], u_{y}^{1}[i]\}\}$$V_{z}[i]$$=$$\{u_{z}^{k}[i]|1\leq k\leq 3\}$$E_{z}[i]$$=$$\{\{u_{z}^{1}[i], u_{z}^{2}[i]\}, \{u_{z}^{2}[i], u^{3}[zi]\}, \{u_{z}^{31}[i], uz[i]\}\}$

は,,からなる.

さらに,$M$$V_{M}=\{c_{ijk}|(x_{i}, y_{j}, zk)\in M\}$とし,$x_{i}$

が $M$ に $B_{x_{i}}(\leq 3)$ 回出現するとき,$x_{i}$が出現するの元を$=$$m_{x;}^{\ell}$$(_{X_{i,y_{j\prime}}}.’$(1 \leq l\leq B)x_{i}$Z_{k_{l}})$とする. このとき,$E_{x}’[i]$とする. 同様に,と$y_{j}$$z_{k}$$=$$\{\{Ci,j_{\ell},k_{\ell},u[pxi]\}|1\leq l\leq B_{x_{i}}\}$

が $M$ にそれぞれ$B_{y_{j}},$$B_{z_{k}}(\leq 3)$回出現するとし,$y_{j},$$z_{k}$が出現する $M$ のそれぞれの元を$m_{yj}^{\ell}$$=$$(x_{i_{l}y_{j}},, z_{k},.)$$(1 \leq\ell\leq B_{yj})$$m_{z_{k}}^{l}$$=$$(x_{i_{\ell}}, y_{j\prime’ k}.z)$$(1\leq l\leq B_{z_{k}})$,とする. このとき,$E_{y}’[j]$$E_{z}’1^{k}]$とする. このとき,$G_{2}=(V_{2}, E_{2})$$V_{2}$$=$$E_{2}$$=$$=$$\{\{_{C_{i_{l},j,\mathit{1}}}k,u_{y}^{l}[j]\}|1\leq^{p\leq}B\}yj$$=$$\{\{_{C,u^{l}}i_{P},j_{\ell,k}z[k]\}|1\leq\ell\leq B_{z_{k}}\}$’は以下のように表される.

$V_{M} \cup(_{(x_{i},y_{j},z}\bigcup_{k)\in}(V_{x}[i]\cup V_{y}[j]\cup V_{z}[k]))M^{\cdot}$.

$x_{iyj} \bigcup_{(,,zk)\in M}(Ex[i]\cup E_{y}[j]\cup E_{z}1k]\cup E_{x}’[i]\cup E\mathrm{b}]\cup E[kyz\prime\prime])$17$\mathrm{z}_{1}$

図 4: MAX

以上が$G_{1}$$G_{2}$と性質 1.

Z3$\mathrm{z}_{2}$$3\mathrm{D}\mathrm{M}$$\mathrm{Z}|\mathrm{z}\mathrm{J}- \mathrm{l}$のある入力に対応するグラフ$\mathrm{z}_{2_{\aleph}1}$$G_{2}$の構成法である (図 4 参照).
$G_{2}$$G_{2}$は, 以下の性質をもっている.の中で,$K_{3}$と同型なグラフは,$G_{x}[i](1\leq i\leq|X_{M}|)$,$G_{y}[i](1\leq i\leq|Y_{M}|)$,$G_{z}[i](1\leq i\leq|Z_{M}|)$のみである.

性質 2. 任意の $G[i](1\leq i\leq|Z_{M}|)$ と同型な

$G_{2}$の誘導部分グラフは,$G_{2}|_{V_{x}[r}]\cup Vv1s]\cup V_{z}[t]\cup\{c_{\delta\iota},\}$$((x_{r}, y_{S}, zt)\in M)$

のみである.

性質 1 および性質 2 より,$U$の誘導部分グラフ$G|_{U}$MAX 3DM-B の最適解のコストを OPT $(I)$ としたとき, 以下の頂点集合
は, MAX CIS-B の入力 $f(I)$ に対する最適解の一つである.

$U$

$=$

$(^{OPT(I)} \bigcup_{i=1}V[i]\mathrm{I}\cup(|\bigcup_{i=OP\tau(I)+1}^{z}(V[i\underline{\rceil}M|--\{a[i]\}))$.

これは,$G[i](1\leq i\leq OPT(I))$ ,からなる$G_{1}$の誘導部分グラフに同型なグラフである. これより,$oPT(f(I))$

である.

$G[i]|\{v_{j}^{k}[i]|1\leq j\leq 3,1\leq k\leq 3\}(OPT(I)+1\leq i\leq|Z_{M}|)$$=$

10 $\cdot OP\tau(I)+9(|Z_{M}|-OP\tau(I))$$\leq$$27B\cdot OP\tau(I)+OP\tau(I)$$=$$(27B+1)\cdot OPT(I)$18
さらに,コスト c2 をもつ MAX CIS-B の入力 $f(I)$ の任意の解に対して,.

$\{C:,j,k\}\cup Vx[i]\cup\dot{V}_{y}[j]\cup V_{z}[k]$$\sim$がその解に入っているときに限り,$(x_{i}, yj, z_{k})$を MAX$3\mathrm{D}\mathrm{M}$の入力ぶものとする. そのようにして得られるマッチングの解がコスト$|OPT(I)-c_{1}1$をもつ MAX$I$のマッチングの解の–つとして選をもっとすれば,$c_{1}$$|OPT(f(I))-c2|$$\leq$の解を多項式時間で見つけることができる. 従って, 次数制
限最大共通誘導部分グラフ問題は, 最大 3 次元マッチング問題から 還元可能である.となるコスト$c_{1}$の入力$3\mathrm{D}\mathrm{M}$

$I$

$L$

口

入力される 2 つのグラフの頂点数と辺の数がともに等しい MAX CIS-B および MAX CIS-CB, さらに入力される 2 つのグラフの頂点数と辺の数がともに等しい MAX CIS-CB の 3 つの問題についても,

3DM-B から

$L$MAX還元することによって, 以下の定理が証明される. 上で示した証明とくらべると以下の証明で作られるグラフは, 条件が加えられているほど複雑になっている.
定理 4. $B\geq 3$ であり, かつ入力される 2 つのグラフの頂点数と辺の数がともに等しいとき,

MAX CIS-B

は MAX SNP-hard である.

定理 5. MAX CIS-CB は,定理 6.
$\mathrm{C}\mathrm{B}$

4$B\geq 3$$B\geq 3$のとき MAXSNP-hard である.

であり, かつ入力される 2 つのグラフの頂点数と辺の数がともに等しいとき,

MAX CIS-は MAX SNP-hard である.

最大共通誘導部分グラフ決定問題の$\mathrm{N}\mathrm{P}$

完全性についてこの章では, 入力される 2 つのグラフの頂点の次数が高々 2 のときに, 次数制限最大共通誘導部分グラフ問題 (決定問題) が$\mathrm{N}\mathrm{P}$完全であることを示す. 次数制限最大共通誘導部分グラフ問題の$\mathrm{N}\mathrm{P}$

完全性を議論するために, 決定問題として次のように定義する.

次数制限最大共通誘導部分グラフ問題 (決定問題) (MAXIMUM BOUNDED COMMON INDUCEDSUBGRAPH (MAX CIS-B)$)$

入力: 無向グラフ $G_{1}=(V_{1}, E_{1}),$ $c2=(V_{2}, E_{2})$ , 正定数 $K$ .

ただし,$G_{1},$ $G_{2}$の次数はともに最大 $B\geq 0$ であるとする.

問題: 頂点数が $K$ 以上の$G_{1},$$G_{2}$の共通誘導部分グラフが存在するか.

本章では, 次の問題から MAX CIS-B への還元を考える.

3 分割問題 (3-PARTITION)
入力: 有限集合 $A$ , 正定数 $L,$ $A$ から正定数への関数
ただし, 任意の $s(a)$ に対して,$\frac{L}{4}<s(a)<\frac{L}{2}$

問題: $A$ を互いに交わりのない $m$ 個の集合
ただし,$1\leq i\leq m$に対して,$S_{1},$ $S_{2},$$s$.

である. また,$\cdots,$$\sum_{a\in s_{:^{s}}}(a)=L$$S_{m}$$\sum_{a\in A}s(a)=mL$に分けることができるか.

.

19
定理 7. MAX CIS-B は $B\geq 2$ のとき
証明.

$\mathrm{N}\mathrm{P}$完全である.

3-PARTITION からの還元である。

口

入力される 2 つのグラフの頂点数と辺の数がともに等しい MAX CIS-B についても, 3-PARTITIONから還元することによって, 以下の定理が証明される.
定理 8. $B\geq 2$ であり, かつ入力される 2 っのグラフの頂点数と辺の数がともに等しいとき, MAX CIS-B.
は完全である.
$\mathrm{N}\mathrm{P}$5

結論
本論文では,小さな次数に制限した最大共通誘導部分グラフ問題の計算量について考察した. 結果をまとめると表 1 のようになる. 入力として与えられる 2 つのグラフの次数がともに高々 2 であるときに,PTAS があるか, それとも MAX SNP-hard であるか, また, 入力として与えられる 2 つのグラフの次数がともに高々 3 であるときに,MAX SNP 完全かという課題が残されている.

表 1: まとめ参考文献[1] T. Jiang, L. Wang, and K. Zhang. Aligment of trees
Computer Science, pp. 137-148, 1995.

-an alternative to tree edit. Theoretical[2] V. Kann. Maximum bounded 3-dimensional matching is
cessing Letters, Vol. 37, pp. 27-35, 1991.

$\max \mathrm{s}\mathrm{n}\mathrm{p}$-complete.

Imformation Pro-

[3] V. Kann. On the approximability of the maximum common subgraph problem. In STACS 92,pp. 377-388, 1992.

[4] E. Kubika, G. Kubicki, and I. Valalis. Using graphpp. 43-48.

distanc.e in object recognition. In,$ACM\mathit{9}\mathit{0}$[5] B. Zelinka. Distances between graphs. In 4th Czechoslovakian Symposium on Combinatorics,Graphs and Complexity, pp. 355-361, 1992.