数理解析研究所講究録
第 833 巻 1993 年 186-196186

形式グラフ体系上の反駁木問題の並列化とグラフ同型問題
内田智之 \dag er

正代隆義 \dager

宮野悟 *(Tomoyuki Uchida)(Takayoshi Shoudai)(Satoru Miyano)\dag er :\d ag er :*:九州大学大学院総合理工学研究科情報システム学専攻
山口大学工学部
九州大学理学部附属基礎情報学研究施設

要旨
形式グラフ体系 (Formal Graph System, FGS) は, 文字列を論理プログラムの項として扱う基本形式体系 (Elementary Formal System) を, グラフを項として扱えるように拡張したグラフ生成システムである. 論理プログラムと同様に FGS 上で反駁木を定義し, 与えられたグラフの反駁木を構築する反駁木問題について考察する. FGS の部分クラスであるサイズ
限定単純 FGS に対する反駁木問題がグラフ同型問題に $NC^{2}$ 還元可能であることを示す. さらに,アトムに現れる変数の出現回数が高々 1 回であるようなサイズ限定単純 FGS 上の反駁

木問題は $NC^{2}$ に属すことを示す. また, サイズ限定 FGS$\Gamma$を与え,$\Gamma$

上の反駁木問題は,本質的にグラフ同型問題を含むことを示す.

1

はじめに
形式グラフ体系 (Formal Graph System, FGS) は, 論理プログラムの項として文字列を扱う

基本形式体系 (Elementary Formal System) $[2, 9]$ を, グラフを項として扱えるように拡張した新

しい形式体系である [10]. また,

FGS は, グラフがどのように生成されるかを明瞭かっ簡潔に表現できる論理プログラムである.

FGS の部分クラスである正則 FGS が, 文脈自由グラフ文法[6] と同等の生成能力をもっことが内田ら [10] により示されている. 本稿では, 論理プログラムと同様に,

FGS 上で反駁木を定義し, 与えられたグラフの反駁木を構築する反駁木問題について考察する. 反駁木は, 与えられたグラフがどのようにして生成されたかを示す木であり, 与えられたグラフに divide-and-conquer 技法をどのように適用すればよいかの指針を与える木である.

したがって, 反駁木問題を解くことは,

多くのグラフ上の問題に対する効率よい並列アルゴ

Mailing address: Research Institute of Fundamental Information Science, Kyushu University 33, Fukuoka
812, Japan (e-mail: uchida@rifis.sci.kyushu-u.ac.jp, shoudai@rifis.sci.kyushu-u.ac.jp, miyano@rifis.sci.kyushu-

u.ac jp).

187
リズムの設計に非常に有用であると考えられる. 例えば, インスタンスを反駁木が NC で求められるようなグラフに制限することにより, 多くの NP 完全な問題が NC に入ることを示すことができる $[4, 8]$. 内田ら [10] は, Two-terminal series parallel グラフの族および外平面的グラフの族を定義するそれぞれの FGS に対し, 反駁木問題を解く効率のよい並列アルゴリズムを与えている.

一般の FGS に対する反駁木問題を解くにはグラフ同型問題を解く必要がある. 本稿の目的は,反駁木問題とグラフ同型問題との関係を明確にすることにある. まず, 反駁木問題からグラフ同

FGS の部分クラスであるサイズ限定単純 FGS に対する反駁木問題は型問題への還元を与える.

グラフ同型問題に $NC^{2}$ 還元可能であることを示す. また, 単純 FGS により生成されるグラフの族は次数限定グラフの族に含まれることを示す. これにより, 次数限定グラフに対するグラフ同型問題は多項式時間で解ける [5] ことから, サイズ限定単純 FGS に対する反駁木問題は多項式時間で解ける. また, 次数限定木に対するグラフ同型問題は NC に入る [1] ので, 次数限定木を生成するサイズ限定単純 FGS に対する反駁木問題は NC に属する. さらに,アトムに現れる変数の出現回数が高々 1 回であるようなサイズ限定単純 FGS に対する反駁木問題は $NC^{2}$ に入ることを示す. また, サイズ限定 FGS$\Gamma$を与え,$\Gamma$

上の反駁木問題は, 本質的にグラフ同型問題を含むことを示す.

2

形式グラフ体系と反駁木問題$\Sigma$1)と $X$ を互いに素な有限アルファベットとし,$x,$ $y,$$\ldots$

で表し, 引数をもっ述語記号を $p,$ $q,$を, 頂点の集合 $V$ , 辺の集合 $E$ , 写像

(V, $E,$る.

$\varphi,$$\psi$) で定義する.

ラベル頂点の集合を

$Z$

に対し,

$\mathcal{N}(G, v)$

ある集合 $Z$ に対し,

を

$v$

$Z$

グラフという.

$E$する. このとき,$N\cross N$

$E$

の元の数を
$E_{U}$$\neq Z$への関数とする.

以下の条件を満たす$\psi$

$\Pi$

$x$

とする.

$F$

このとき,

$\prime r(\Sigma\cup x)$$X$$\overline{\psi}(Z)$中の $Z$

また,

$Z$

の元で

で表す.

$V$

の頂点

$E(v)$ を $v$ に付随する $E$ 中の辺の集合とする.
$V$の部分集合 $U$ に対し, 両端点が $U$ に含まれ$G[U]=$( , Eu,$U$$\varphi,$$\psi$

)を

$U$

$x$

の頂点誘導部分に属する辺の端点からなる $V$ の部分集合を $V(F)$ とを $F$ の辺誘導部分グラフという.

の元

$V$

ラベル頂点を変数頂点という.

このとき,$=(V(F), F, \varphi, \psi)$に対し,とする. グラフ

または多重グラフであ$x$$deg$ を $X$ からの位数を $deg(x)$ で定義する.

に属するグラフ $G=(V, E, \varphi, \psi)$ を項グラフという.

1. 任意の 2 っの変数頂点は隣接しない.

2. 任意の変数の元を変数とい: $Earrow\Sigma\cup N$ の 4 つ組 $G=$

中の $Z$ ラベル辺の集合をで表す.

の部分集合 $F$ に対し,
$E\{F\rangle$$X$の隣接頂点の集合とし,るような $E$ 中の辺の集合を$X$, で表し, その有限集合をは無向グラフ, 有向グラフ,

とくに,ラベルづけられた辺を $Z$ ラベル辺とい 1)
$v$

とする.

の元でラベルづけられた頂点を $Z$ ラベル頂点とい 1)

とかく.

$\tilde{\varphi}(Z)$$\ldots$: $Varrow\Sigma\cup X$ , 写像

$G=(V, E, \varphi, \psi)$

に対し,$Z\subseteq\Sigma\cup X$$\varphi$$N=\{0,1, \ldots\}$

でラベルづけられた頂点の次数は $deg(x)$ である.

$N\cup$188
3. $e\in E$ が変数頂点に付随する辺ならば,
点
$p$

を

に付随する異なる 2 っの辺$v$$n\exists|$

数の述語記号,

とくに,う.

$g_{1},$$\ldots,$

をアトムとする.

$\ldots,$$e_{2}$

に対し,$1\leq\psi(e_{1})\neq\psi(e_{2})\leq\neq E(v)$を項グラフとする.

このとき,$p(g_{1}, \ldots, g_{n})$であるアトム $p(g_{I}, \ldots, g_{n})$ を基礎アトムという.

$g_{n}\in\prime r(\Sigma)$

このとき,$g_{n}$とグラフ書換規則とは,$Aarrow B_{1},$$\ldots,$.

をアトムとい$A,$ $B_{1},$$\ldots,$$B_{n}$の形をした節であ$B_{n}(n\geq 0)$$n=0$ のグラフ書換規則を事実という.

とくに,

る.

$g_{1},$$e_{1}$

かっそのときに限る. 変数頂$\psi(e)\in N$ であり,

定義 1. 形式グラフ体系 (Formal Graph System, FGS) とは, グラフ書換規則の有限集合で
ある.

2 項関係

を次のように定義する. 無向グラフである項グラフ $g_{1}=(V_{1}, E_{1}, \varphi_{1}, \psi_{1})$ と $g_{2}=$$\simeq$$(V_{2}, E_{2}, \varphi_{2}, \psi_{2})$に対し,とは, 以下の条件を満たす同型写像$g_{1}\simeq g_{2}$

$\pi$

:

$V_{1}arrow$

巧が存在すると

きをいう.

1.

に対し,

$u\in V_{1}$$\varphi_{1}(u)=\varphi_{2}(\pi(u))$

2. $\{u,v\}\in E_{1}$ に対し,.

$\psi_{1}(\{u, v\})=\psi_{2}(\{\pi(u), \pi(v)\})$.

項グラフが有向グラフおよび多重グラフである場合も同様に定義される. アトム $p(f_{1}, \ldots, f_{n})$ とに対し,$p(g_{1}, \ldots, g_{n})$$p(f_{1}, \ldots, f_{n})\simeq p(g_{1}, \ldots, g_{n})$とは, 各 $i(1\leq i\leq n)$ に対しゐ$\simeq g_{i}$であるときをいう.
$x_{1},$個の$\ldots,$$x_{n}$

を相異なる変数,

ラベル頂点の列とする.

$\Sigma$

代入 (substitution) という.
する.

$g_{1},$

このとき,$\theta$によるられる項グラフをいう.

$g$$\ldots,$$g_{n}$$g=(V, E, \varphi, \psi)$

$g$

の頂点

$v_{i}^{deg(x_{i})}$$v_{i^{1}},$$\ldots,$$j\leq deg(x_{i}))$$\theta$$\sigma_{i}(i\leq i\leq n)$を項グラフ,$\Sigma$と$A_{2}$

をそれぞれ同一視し,である. その後, 変数頂点

$v$

$g$

に

$g_{i}$$arrow B_{1},$$\ldots,$$A_{1}$

は$A_{2}$,$\square$

$g$

の頂点

を連結する. なお,$\ldots,$$B_{m}$$u_{i}^{1},$$\ldots$$g$から得$u_{i}^{j}(1\leq$,$u_{i}^{deg(x;)}$と$\varphi’(u_{i}^{j})=\varphi(u_{i}^{j})(1\leq$に対し,$(Aarrow B_{1}, \ldots, B_{m})\theta=A\thetaarrow B_{1}\theta,$

このとき,の変種 (variant) という.

$B_{1},$$\theta$と$\ldots,$$\theta’$$B_{m}$$B_{m}\theta$$\ldots,$$A_{1}\theta\simeq A_{2}\theta$に対し,$B_{m}(m\geq 0)$ の形のグラフ書換規則をゴールというを空節とい 1)

, . . . , $v_{i}^{deg(x_{i})})(1 \leq i\leq n)$ ととそれに付随する $E(v)$ の辺を取り除く. また, 代入の単一化代入 (unifier) という. また, ある代入であるとき,$\sigma_{i}=(v_{i^{1}}$ラベル頂点とする. まず,を 2 っの項グラフまたはアトムとする.

$A_{2}$の相異なる $deg(x_{i})$の $x_{i}(1\leq i\leq n)$ でラベ)\iota /づけられた各変数頂点 $v$ に対し,$p(f_{1}, \ldots, f_{n})\theta=p(f_{i}\theta, \ldots, f_{n}\theta)$と$g_{i}$の例 (instance) $g\theta=(V’, E’, \varphi’, \psi’)$ とは次のようにして, アトム $p(f1\cdots, f_{n})$ , およびグラフ書換規則 $Aarrow B_{1},$$A_{1}$

をこのとき, 有限集合 $\theta=\{x_{1} :=(g_{1}, \sigma_{1}), \ldots, x_{n} :=(g_{n}, \sigma_{n})\}$ を$j\leq deg(x_{i}))$ を $\psi(\{v, u_{i}^{j}\})=i$ である$g_{i}$

を項グラフ,と定義する.

である代入$A_{1}\simeq A_{2}\theta$

をアトムとする.

. とくに,かっ$\theta$を$A_{1}$$A_{1}\theta’\simeq A_{2}$

このとき,$m=0$ のときのゴール

で表す.

グラフ書換規則 $C$ に対し,$v(C)$ を $C$ に現れるすべての変数の集合とする.

あるアトムを選ぶために計算規則 $Q$ を仮定する.

$\Gamma$をある FGS,$D$を$\Gamma$

あるゴールからのゴールとする. 論理

189
プログラムと同様に,$D$からの導出 (derivation) とは, 以下の条件 (1),(2) $)(3)$ を満たす 3 っ組の列である:$(D_{i}, \theta_{i}, C_{i})(i=0,1, \ldots, )$

(1)

はゴール,

$D_{i}$(2) 相違なる$\emptyset$(3)$i,$ $j$

はある代入,$\theta_{i}$に対し,$C_{i}$

は$\Gamma$のグラフ書換規則の変種であり,$v(C_{i})\cap v(C_{j})=\emptyset$

である.

また, すべての$i$$D_{0}=D$ である.

について $v(C_{i})\cap v(D)=$である.

$D_{i}$

がゴール $arrow A_{1},$$\ldots,$$C_{i}=Aarrow B_{1},$ $\ldots,$ $B_{q}$$A_{m+1},$ $\ldots,A_{k}$)$A_{k}$,$\theta_{i}$であり,が $A$ とが $Q$ により選ばれたアトムならば,$A_{m}$$A_{m}$の単一化代入,$D_{i+1}=(arrow A_{1},$ $\ldots,$ $A_{m-1},$ $B_{1},$ $\ldots,$ $B_{q}$である.

$\theta_{i}$また, 空節で終わる有限導出を反駁という.

$F$をゴール $D$ からの反駁とする.

このとき, 次のように定義される木を $F$ の反駁木という.

(1) 木の根はゴール $D$ である.
(2) 木の葉はすべて空節である.

(3) 導出 ($D_{i},$の頭部$\theta_{i}$$A_{i}$, Ci) の各ステップにおいて,$\theta_{i}$が$D_{i}$のあるアトム $A$ と $C_{i}=A_{i}arrow B_{1},$$B_{k}$$\ldots,$の単一化代入であるならば, 木の頂点 $A$ はすべての $B_{j}\theta_{i}(1\leq j\leq k)$ に有向辺をもつ.
グラフ書換規則 $C$ が代入およびモーダスポーネンスの有限回の適用により FGS
るとき,

$C$

は

$\Gamma$から証明可能であるとい$A$)$\Gamma\vdash C$

とかく. っまり, 関係$\Gamma$から得られは次のように$\Gamma\vdash C$

帰納的に定義される.

(1)$C\in\Gamma$

ならば,

(2)

$\Gamma\vdash C$

ならば, 任意の代入(3)$\Gamma\vdash Aarrow B_{1},$ $\ldots,B_{m},$また, 一引数の述語記号

ある言語$L\subseteq\prime r(\Sigma)$

である.

$\Gamma\vdash C$$\theta$$B_{m+1}$

$P$

に対し,

である.

かっ $\Gamma\vdash B_{m+1}$ ならば,,$\Gamma\vdash Aarrow B_{1},$$\ldots,$$B_{m}$

である.

に対し, 言語 $GL(\Gamma,p)$ を $\{g\in\prime r(\Sigma)|\Gamma\vdash p(g)arrow\}$ と定義する.

が FGS 言語であるとは,在するときをいう. 集合 $B(\Gamma)=$ {$SS(\Gamma)=$$\Gamma\vdash C\theta$$p(g_{1},$$\ldots,$$L=GL(\Gamma,p)$ である FGS$g_{n})|P\in\Pi$ かっ$g_{1},$$\ldots${ $A\in B(\Gamma)|arrow A$ からの反駁が存在する} とする. 集合 PS,$\Gamma$と述語記号$g_{n}\in\prime r(\Sigma)$$(\Gamma)$

を$\Gamma$

定義 2. FGS$\Gamma$$\Gamma$に対し,から証明可能なす

SS(F) $=PS(\Gamma)$ .

と一引数の述語記号$p$上の反駁木問題 $(RT(\Gamma,p))$ を次のように定義する.

INSTANCE:

グラフ $G$ .

PROBLEM:

もし $G$ の反駁木が存在するならばその木を構築せよ.

命題 1 より, 反駁木問題は認識問題と一致する.

が存} とし, 集合

べての基礎アトムの集合とする.
命題 1. すべての FGS

$p$

,

190
サイズ限定単純 FGS 上の反駁木問題からグラフ同型問題への還元

3$g=(V, E, \varphi, \psi)$

をある項グラフとする.

$E|e$ の端点が変数頂点である} とする.
$(\neq V, \neq E’)$

る.

$V’$

このとき,

$g$

のサイズ (

で定義する. アトム $p(g_{1}, \ldots, g_{n})$ に対し,

グラフ書換規則 $Aarrow B_{1},$$||B_{1}\theta||+\cdots+\Vert B_{m}\theta\Vert$$\ldots,$$B_{m}$$|g|$とかく) を頂点数と辺数の組$\Vert p(g_{1}, \ldots, g_{n})\Vert=|g_{1}|+\cdots+|g_{n}|$がサイズ限定であるとは, 任意の代入であるときをいう.

FGS$:=E-\{e\in$$:=V-\{v,\mathcal{N}(g, v)|\varphi(v)\in X\},$ $E’$$\Gamma$

がサイズ限定であるとは,に対し,$\theta$$\Gamma$とす$\Vert A\theta||\geq$のすべてのグラフ

書換規則がサイズ限定であるときをいう. 以後, グラフ書換規則を単に規則ということにする.

2 項関係$\sim$

を次のように定義する. 無向グラフである項グラフ$(V_{2}, E_{2}, \varphi_{2}, \psi_{2})$に対し,$g_{1}\sim g_{2}$$g_{1}=(V_{1}, E_{1}, \varphi_{1}, \psi_{1})$とは, 以下の条件 (1) と (2) を満たす同型写像

$\pi$

:

と $g_{2}=$$V_{1}arrow V_{2}$が存在するときをいう.

(1) 任意の頂点 $u\in V_{1}$ に対し,$\varphi_{1}(u)=\varphi_{2}(\pi(u))$(2) $\varphi_{1}(\{u, v\})\in N$ である辺 $\{u, v\}\in E_{1}$ に対し,.
$\psi_{1}(\{u, v\})=\psi_{2}(\{\pi(u), \pi(v)\})$.

項グラフが有向グラフまたは多重グラフである場合も同様に定義される.
すべての辺が $a\in\Sigma$ でラベルづけられているグラフからなる $lr(\Sigma)$ の部分集合を$\Psi_{a}$とする.

Shield を任意の述語記号 p に対し \Psi a に属する p の引数個のグラフの列をかえす関数とする. 規則$q_{0}(g_{0}^{1}, \ldots,g_{0^{0}}^{l})arrow q_{1}(g_{1}^{1}, \ldots,g_{1^{1}}^{l}),$$\ldots,q_{k}(g_{k}^{1}, \ldots,g_{k^{k}}^{l})(k\geq 0)$が以下の条件を満たすとき, その規則は単純であるという.
$i\leq k,$ $1\leq l_{i}\leq l,$ $1\leq j\leq$のは連結項グラフであり,$q_{i}$

ここで,$g_{i}^{j}=(V_{i}^{j}, E_{i}^{j}, \varphi_{i}^{;},\dot{\psi}_{i})(0\leq$は Shield $(q_{i})=(h_{i}^{1}$ , . . . ,$h_{i^{\mathfrak{i}}}^{l})$である$l_{i}$

引数の述語記号である.

(I) 各項グラフ $d(1\leq i\leq k, 1\leq j\leq l_{i})$ は以下の条件 (i),(ii),(iii) を満たす.
(i) 複数の変数頂点に隣接する頂点は存在しない.
(ii)$g_{i}^{i}$[ $V_{i^{j}}-\{u,$ $v|u\in$ 姦$(X),\mathcal{N}(\dot{f}_{i},$$v)=\{u\}\}$ ]$\simeq h_{i}^{j}$.

(iii) 以下の条件 (a) と (b) を満たす項グラフ $g=(V, E, \varphi, \psi)$ を部分グラフとしてもつ頭部の項グラフ$g_{0}^{l}$(a).
(b) 任意の頂点が存在する.

$g\sim\dot{d}$(II) 各項グラフ$v\in\{\mathcal{N}(g, u)|u\in\tilde{\varphi}(X)\}$$g_{0}^{l}(1\leq l\leq l_{0})$(1)$\{a\}$(2)$E_{0}^{l}\langle\tilde{\psi}_{0}^{l}(\{a\})\rangle\simeq h_{0}^{l}$に対し,$\mathcal{N}(g, v)=\mathcal{N}(g_{0}^{l}, v)$.

は以下の条件 (1),(2),(3) を満たす.

ラベル辺が存在するならば, 複数の変数頂点に隣接する頂点は存在しない.

.

(3) 変数頂点の隣接頂点を端点にもっグラフ

1$(1\leq i\leq k, 1\leq j\leq l_{i})$$\{a\}$

ラベル辺が存在するならば,が存在する.

$g_{0}^{l}\simeq$

屑である項

191
FGSF が単純であるとは, F のすべての規則が単純であるときをいう.
補題 1.

$\Gamma$

を単純 FGS とし,$P$をに現れる述語記号とする.

$\Gamma$

このとき,$GL(\Gamma,p)$は次数限定に現れる述語記号とする.

このとき,$RT(\Gamma,p)$グラフの族に含まれる.
定理 1.

$\Gamma$

をサイズ限定単純 FGS とし,$P$を$\Gamma$はグラフ同型問題に $NC^{2}$ 還元可能である.
証明: 入力となるグラフ $G=(V, E, \varphi, \psi)$ を $V=\{1, \ldots, n\}$ である無向グラフとする.
パスシステム $P=$ ( $N,$ $T$ , GEN, s)

の集合,

$T$

は $N$ の部分集合,$[3, 7]$ を次のように構築する.

ここで,GEN は $N\cup(N\cross N)\cup\cdots\cup N^{k}$ から$2^{N}$$N$

はシステムの元への関数 ( : 定数),
$k$

$s$

は $N$ のある元である.

パスシステム $P$ の元の集合 $N$ を集合

MakeAtom とは, 入力としてで,うな操作である.

$l$をある正定数,$\Gamma$

$k$

規則

$|$

$r\in\Gamma$} $\cup\{p(G)\}$ とする. ここの規則が与えられたときにアトムの集合を出力する次のよを負でない定数$(V_{i}^{j}, E_{i}^{j}, \varphi_{i}^{j}, \psi_{i}^{j})(0\leq i\leq k, 1\leq i\leq l_{i})$き,{MakeAtom(r)を連結項グラフ,$1\leq l_{0},$$q_{i}$

を$\ldots,$$l_{i}$とする. また,$l_{k}\leq l$

引数の述語記号とする.

F を以下のような規則 r からなると仮定しても一般性を失わない.
$q_{k}(g_{k’}^{1}g_{k^{k}}^{l})$$q_{0}(g_{0}^{1}, \ldots, g_{0^{0}}^{l})arrow q_{1}(g_{1}^{1}, \ldots, g_{1^{1}}^{l}),$$\ldots,$.

この規 $H|Jr$ が入力として与えられたときの手続き MakeAtom を以下に示す.

Procedure MakeAtom(r: a rule): Set;
1. If が事実である then
$r$

2.

$U$

$:=\{[q_{0}, a_{1}, \ldots, a_{l_{0}}]|a_{j}\in MakeTerm(g_{0}^{j}), 1\leq j\leq l_{0}\}$;3. else;4.

$U:=\emptyset$

5

For $i:=1$ to

6.

7.

$k$

do

$U$ $:=U\cup\{[q_{i}, a_{1}, \ldots, a_{l_{\mathfrak{i}}}]|a_{j}\in MakeTerm(\dot{f}_{i}), 1\leq j\leq l_{i}\}$od
Output$U$;$g_{i^{j}}=$

このと

192
Procedure $Mal\sigma eTerm$ ( $g=(V_{g},$$E_{g},$$\varphi_{g},$$\psi_{g})$: a term graph): Set;

1.

$8:=\#$ ( $E_{g}-\{e\in E_{g}|e$ の端点が変数頂点である});2.

$c:=\#\tilde{\varphi}_{g}(X)$3.

$t_{v}$

4.

$F:=$

;

$:=g$ の頂点 $v$ の次数;{$(e_{1},$$\ldots,$$e_{s})|e_{1},$$\ldots,$$e_{s}$

は互いに異なる $E$ の元};

5. If $c=0$ then6.

$|B\in F,$ $E\{B\rangle\simeq g\}$

$Z$ $:=Z\cup\{\{B\rangle$;

7. else
8.

$g$

9.

の変数頂点をソートする関数を計算する;{ $e\in E_{g}|e$ の端点が変数頂点である} をソートする関数$E_{g}-$

10.

$I$

$J$

を計算する;For $(e_{1}, \ldots, e_{s})\in F$ pardo

For

11.

12.

$D_{v}^{(e_{1},\ldots,e_{\iota})}$

13.

odpar

14.

$M^{(e_{1},\ldots,e_{s})}$

15.

odpar

16.

then

pardo

$v\in\overline{\varphi}_{g}(X)$$:=\{(u_{1}, \ldots, u_{t_{v}})|u_{i}\neq u_{j}\in e_{1}\cup\cdots\cup e_{s}, 1\leq i\neq j\leq t_{v}\}$$:=\{(d_{v_{1}}, \ldots, d_{v_{c}})|v_{i}\in\tilde{\varphi}_{g}(X), d_{v_{\mathfrak{i}}}\in D_{v}^{(e_{1},\ldots,e_{\delta})}, 1\leq i\leq c\}$\ldots, u_{i^{1}}^{t})(1\leq i\leq c)$ とする.
$d=(u_{i}\pi^{v_{\iota}}:(e_{1}\cup^{1}\cdots\cup e_{s})arrow V_{g}-\tilde{\varphi}_{g}(X)$$(II)\text{を^{}(}\text{満^{}d}m$$(I^{e})^{s}$

以下の条件

;

} $|f\in F$ と $m\in M^{f}$ は以下の条件を満たす};$Z$ $:=Z\cup\{\langle f,$ $m$$f=$ $(e_{1},17.

;たす同型写像とすが存る在し, かっ CAeck $(g, \langle(e_{1}, \ldots, e_{s}), (d_{v_{1}}, \ldots, d_{v_{c}})\rangle)=true$ である.

(I) 各 $e_{i}(1\leq i\leq s)$ に対し, 対応する(II) 各 $i(1\leq i\leq c)$ に対し,ある

Output

$g$

の変数頂点

$v$

$g$

上の辺の

$J$

の値は

$i$

$\{\pi(u_{i}^{1}), \ldots, \pi(u:\cdot)\}=\mathcal{N}(g, v)$が存在する.

$Z$

Procedure Check( : a term graph, : a sequence): boolean;
$d$

$g$

$/*g=(V_{g}, E_{g}, \varphi_{g}, \psi_{g});d=\{(e_{1}, \ldots, e_{s}),$ $(\eta_{1}, \ldots, \eta_{c})\rangle$ $;*/$$1$. $D:=false$ ;2. For

3
4

$g$

If

中の各変数

$x$

pardo

$\neq\tilde{\varphi}_{g}(\{x\})\geq 2$

For

then

$u\in\tilde{\varphi}_{g}(\{x\})$

pardo

である.
かっ $I(v)=i$ で

193
5.

$\eta_{I(u)}$の頂点を含む $G-\{e_{1}, \ldots, e_{s}\}$ の成分からなるグラフ

を$B_{I(u)}$

構築する;

6.

odpar

7.

If 任意の

8.

else

9.

else

$C_{x}$$C_{x}$$u,$ $v\in\tilde{\varphi}_{9}(\{x\})$に対し $B_{I(u)}\simeq B_{I(v)}$ then$:=true$ ;$C_{x}$$:=false$ ;$:=true$ ;10. odpar
11. If$g$

中のすべての変数に対し $C_{x}=true$ である then $D$ $:=true$ ;$x$

Output $D$

手続き MakeAtom と MakeTerm は手続き Check を除き対数領域で計算できる. 手続き Check
は, 連結成分を計算する $NC^{2}$ アルゴリズム [3] を用いることにより,ればならない 7 行目を除き$T$$NC^{2}$を集合 {MakeAtom(r)$|$グラフ同型問題を解かなけで計算可能である.

事実$r\in\Gamma$} とし,$s=\{p(G)\}$ とする.

$k$を$\Gamma$の規則の本体にあるアトムの最大数とする. このとき, 関数 GEN は次のように定義される $N\cup N\cross N\cup\cdots\cup N^{k}$ から$2^{N}$

への関数とする.

の元$N$$[q, \{b^{1}, \lambda^{1}\rangle, \ldots, \langle b^{l_{0}}, \lambda^{l_{0}}\rangle]$$[q_{m}, \langle c_{m}^{1}, \delta_{m}^{1}\}, \ldots, \langle c_{m}^{l_{m}}, \delta_{m^{m}}^{l}\}])(m\leq k)$$q(g^{1}, \ldots, g^{l_{0}})arrow q_{1}(f_{1}^{1}$,...,$([q_{1}, \{c_{1}^{1}, \delta_{1}^{1}\rangle, \ldots, \langle c_{1^{1}}^{l}, \delta_{1^{1}}^{l}\}],$$\ldots$$\ldots,$と代入 $\theta=\{x_{1} :=(h_{1}, \sigma_{1}), \ldots, x_{t} :=(h_{t}, \sigma_{t})\}$

またそのときに限る: 頂点の集合 $U\subseteq V$ と辺の集合 $Z\subseteq E$ に対し,が存在するときをい t),の元であるとは, 以下の条件 (i),(ii),(iii) を満たす規則$q_{m}(f_{m}^{1}, \ldots, f_{m^{m}}^{l})$$f_{1}^{l_{1}}),$

が GEN

$U$

の元をもつ辺誘導部分グラフ $E\{E-Z\}$ の連結成分からなるグラフの辺の集合を $B_{(Z,U)}$ とする.
また,を $G$ の辺誘導部分グラフ $E\{Z\cup B_{(Z,U)}\}$ とする.

$H_{(Z,U)}$(i) 代入$\theta$における項グラフ$h_{1},$$h_{t}$$\ldots,$

はすべて $G$ の部分グラフである.

(ii) 規則の頭部における各項グラフ $g^{i}(1\leq i\leq l_{0})$ に対し,

$g_{i}\theta\simeq H_{(b^{\mathfrak{i}},\lambda^{i})}$(iii) 規則の本体における各項グラフ $f_{i}^{j}(1\leq i\leq m, 1\leq i\leq l_{i})$ に対しであり, かっ次の条件を満たす$\pi_{i}^{j}$が存在する.

とは,$f_{i}^{j}$$f_{i}^{j}\theta$の頂点の集合からの変数頂点に隣接しない 2 頂点$\{\pi_{i}^{j}(u), \pi_{i}^{j}(v)\}$が$c_{i}^{;}$の元であるときをい t)$u$と$H_{(c.,\delta_{i}^{j})}$$v$$\{c_{i}^{;},$

である.
$\delta_{i}^{j}\rangle$$\in MakeTerm(f_{i}^{j})$の頂点の集合への同型写像に対し,$\{u, v\}$が

$f_{i}^{j}$の辺である

またそのときに限る.

関数 GEN はグラフ同型問題を解かなければならない部分を除き $NC^{2}$ で計算できる.
$N$の元の個数は$n$

ム $[3, 7]$ が存在する.

は同値であり,の多項式時間でおさえられるので, パスシステム $P$ を解 \langle $NC^{2}$ アルゴリズ
システム $P$ が解けることと$RT(\Gamma,p)$$s$

が GEN を用いて $T$ から生成されることとはグラフ同型問題に $NC^{2}$ 還元可能である.

入力となるグラフが有向グラフまたは多重グラフのときも同様の結果が得られる.
$(Q.E.D)$

194

図 1: FGS$\Gamma$と$p$$\Gamma_{GI}$をそれぞれ上述の定理で与えられた FGS と述語記号とする. インスタンスが次数限定グラフに制限されたグラフ同型問題は多項式時間で解ける [5] ことから,で解ける.

$\Gamma$$RT(\Gamma,p)$

を $GL(\Gamma,p)$ が木の族に含まれるようなサイズ限定単純 FGS とし,$p$は多項式時間を$\Gamma$

このとき, 次数限定木に対するグラフ同型問題は NC に入る [1] ので,述語記号とする.

に現れる$RT(\Gamma,p)$は NC に属する.

系 1.

$\Gamma$

を各アトムに現れる変数の出現回数が高々 1 回であるような規則からなるサイズ限定単

純 FGS とし,

4

$P$

を

$\Gamma$に現れる述語記号とする. このとき,$RT(\Gamma,p)$は $NC^{2}$ に属する.

グラフ同型問題から反駁木問題への還元
グラフ同型問題とは, インスタンスとしてグラフ型であるかどうか決定する問題である.

FGS$\Gamma$$G_{1}$と$G_{2}$が与えられたとき,と一引数の述語記号$P$$G_{1}$と$G_{2}$

が同上の反駁木問題 $RT(\Gamma,p)$を決定問題に書き直したものを $DRT(\Gamma,p)$ とする.
定理 2.
る.

$\Gamma_{GI}$を図 1 で与えられるサイズ限定 FGS とし,

このとき,

$p$

を

$\Gamma_{GI}$に現れる一引数の述語記号とす

グラフ同型問題は $DRT(\Gamma_{GI},p)$ に対数領域還元可能である.

証明: グラフ同型問題のインスタンスであるグラフ $G_{1}=(V_{1}, E_{1})$ と $G_{2}=(V_{2}, E_{2})$ に対し,

FGS$\Gamma_{GI}$$E_{1}\cup E_{2}$

上で扱うことのできる次のようなグラフ $G=$ (V, $E,$とする.

$\varphi,$$\psi$) を構築する: ここで,

$e\not\in$195(1) $V=V_{1}\cup V_{2}$ .

(2) $E=E_{1}\cup E_{2}\cup\{e\}$ .

(3) 任意の頂点 $v\in V$ に対し,
$a$

$v$

が

$e$

の端点のとき $\varphi(v)=b$ であり, そうでないとき $\varphi(v)=$である.

(4) 任意の辺 $e’\in E$ に対し,$\psi(e’)=c$ である.

このインスタンスの書き換えは対数領域で計算可能である. また, 明らかに, インスタンスが $G$である $DRT(\Gamma_{GI},p)$ を解くことにより,る.

グラフ$G_{1}$と$G_{2}$

が同型かどうかを決定することができ$(Q.E.D)$

この定理 2 により, 図 1 で与えられる FGS$\Gamma_{GI}$

と述語記号

$p$

上の $DRT(\Gamma_{GI}, p)$ を解くことにより, グラフ同型問題を解くことができる.

参考文献[1] T. Akutsu. An RNC algorithm for finding a largest common subtree of two trees. IEICE
Trans. Inf. & Syst., E75-D:95-101, 1992.
[2] S. Arikawa, S. Miyano, A. Shinohara, T. Shinohara, and A. Yamamoto. Algorithmic
learning theory with elementary formal systems. IEICE Trans. Inf. & Syst., E75-D(4) $:405-$$414$,1992.

[3] A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press,
1988.

[4] Xin He. Efficient parallel algorithms for series parallel graphs. J. Algorithms, 12:409-430,

1991.
[5] E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time.

J. Comput. System Sci., 25;42-65, 1982.
[6] T. Pavlidis. Linear and context-free graph grammars. J. Assoc. Comput. Mach., $19(1):11-$$22$, 1972.

[7] W. Rytter. The complexity of two-way pushdown automata and recursive programs.
Technical report, Combinatorial Algorithms on Words, NATO ASI Series $F:12$ , (SpringerVerlag), 1985.

[8] W. Rytter and T. Szymacha. Parallel algorithms for a class of graphs generated recursively.

Inform. Process. Lett., 30:225-231, 1989.

196[9] R. M. Smullyan. Theory of Formal Systems. Princeton Univ. Press, 1961.

[10] T. Uchida, T. Shoudai, and S. Miyano. Parallel algorithms for refutation tree problem on

formal graph systems. RIFIS-TR-CS-59, Research Institute of Fundamental Information
Science, Kyushu University, July 1992.