Subgraph isomorphism (J. R. ULLMANNのアルゴリズム) #アルゴリズム

グラフ$G_\beta = (V_\beta, E_\beta)$の中に$G_\alpha = (V_\alpha, E_\alpha)$が部分グラフとして存在するかどうかを判断する問題です. $(\#V_\alpha \geq \#V_\beta)$
グラフ埋め込み問題とも言います.

Subgraph isomorphismの解法として, J. R. ULLMANNのアルゴリズム [1] を紹介します.

Outline

$G_\alpha$のノードを, $G_\beta$のノードのどれに対応づけるかを表す(写像)行列$M'$を用意する.
$M'$を用いて同型な埋め込みとなっているか (すなわち$G_\alpha$の枝が, 移した先の$G_\beta$でも保存されているか), チェックする条件を作成.
Brute-Force Tree-Search(力任せ木探索)により, 解を探索
そのときに, 同型ならば"$G_\alpha$の枝が, 移した先の$G_\beta$でも保存されている"という条件を用いて, 探索時に枝刈りを行うことで, より効率よく探索を行う.

$p_\alpha := \#V_\alpha, p_\beta := \#V_\beta$ として, $p_\alpha \times p_\beta$行列$M'$を作成する.
これは$G_\alpha$のノードの$G_\beta$のノードへの対応を表すものであり,

M'_{ij} = 1 \Rightarrow G_\alpha{\rm のノード}iを, G_\betaのノードjに対応させる

ということを意味する. よって, 各行, 各列ともに, 1成分は1つ以下であり, 残りは0とする.

グラフ$G_\alpha, G_\beta$の接続行列をそれぞれ$A, B$とする.
例えば, $G_\alpha$のノード$i$と$j$が接続されているならば, $A_{ij} = 1$で, そうでないならば$A_{ij} = 0$となる.

$M'$によって決まる$G_\alpha$のノード$i, j$の移り先を, それぞれ$i_\beta, j_\beta$とすると,

まず,

\displaystyle (M'B)_{ik} = \sum_{l=1}^{p_\beta}M'_{il}B_{lk} = B_{i_\beta k}

すなわち, $i_\beta$と$G_\beta$のノード$k$が接続されているならばこれは1となり, そうでないならば0となる.

また,

\displaystyle (M'(M'B)^T)_{ij} = \sum_{l=1}^{p_\beta}M'_{il}(M'B)_{jl} = (M'B)_{ji_\beta}

すなわち, $j_\beta$と$i_\beta$が$G_\beta$上で接続されているならば1, そうでないならば0となる.

$M'$が同型な埋め込みであれば, "$G_\alpha$上で, ノード$i$と$j$が接続されているならば、 $G_\beta$上で, ノード$i_\beta$と$j_\beta$も接続される" はずなので, $M'$が同型な埋め込みである十分条件は, $C:= M'(M'B)^T$とすると,

A_{ij} = 1 \Rightarrow C_{ij} = 1 (\forall i, j \in V_\alpha)

となる.

$G_\alpha$の各ノードを$G_\beta$のどのノードに割り当てるかを力任せに調べる. あるノードをどのノードに移すかで一階層をなすような木探索になる. $G_\alpha$の全てのノードを割り振り終わったら, STEP2の条件に当てはめて, 同型な埋め込みとなっているかを調べる.

STEP3の探索をより効率的に行うために, 次の自明な条件を加える. $M'$によって$G_\alpha$のノードが$G_\beta$に移ったとき, $G_\alpha$の枝が, 移した先の$G_\beta$でも保存されている. すなわち

もし$A_{ix} = 1$ならば, $B_{i_\beta x_\beta} = 1$となっていなければならない. (ここで, $i_\beta, x_\beta$は$M'$によって決まるノードに移り先)

よって, STEP3の探索中, $M'_{ij}$は次の条件を満たさないならば0に更新される

A_{ix} = 1 \Rightarrow (\exists \,\, y \,\, s.t. M'_{xy}・B_{jy} = 1)

[1] ULLMANN, Julian R. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 1976, 23.1: 31-42.