Soptq

サブグラフ同型（Subgraph isomorphism problem）問題の説明は次の通りです：2 つのグラフ $G_1$ と $G_2$ が与えられた場合、$G_1$ が $G_2$ のサブグラフと同型かどうかを判断します。まず、$G_1$、$G_2$、およびそれに対応する解（つまり、$G_2$ のサブグラフ $G_s$ が $G_1$ と同型である）を取得した場合、解の中の各点とその点に接続されている各辺を走査し、それらが$G_1$ と対応しているかどうかを確認することで、解の正当性を検証するだけです。したがって、この問題は明らかに NP 問題です。

この問題が同時に NP 困難問題であることを証明するために、クリーク問題をサブグラフ同型問題に帰着させます。具体的には、解が存在するクリーク問題 $<G,k>$ が与えられた場合、つまり $G$ には $k$ 個の点からなるクリーク（つまり、これらの $k$ 個の点が相互に接続されている、つまり、$k$- 完全グラフを構成している）が存在する場合、$G_1$ を $k$- 完全グラフとし、$G_2 = G$ を構築します。明らかに、上記の 2 つのグラフの構築は多項式時間で完了することができます。

もし多項式時間でサブグラフ同型問題を解くアルゴリズム $A_s$ が存在する場合、クリーク問題に対しては、上記の構築に従い、多項式時間でクリーク問題の $k$ と $G$ から $G_1$ と $G_2$ を構築し、それをサブグラフ同型問題のアルゴリズム $A_s$ に与えることで、$G_1$ が $G_2$ のサブグラフと同型であるかどうか、つまり $k$- 完全グラフが $G$ に含まれているかどうかを多項式時間で知ることができます。つまり、クリーク問題を多項式時間で解くことができます。

クリーク問題が NP 完全であることが既知であるため、上記のアルゴリズム $A_s$ は存在しないため、サブグラフ同型問題は NP 困難問題です。以上から、サブグラフ同型問題は NP 完全です。