サブグラフ同型
グラフ G_1=(V_1,E_1), G_2=(V_2,E_2) があります。
質問: グラフ G_1 は G_2 の部分グラフと同形ですか?
(つまり、|V|=|V_1| および |E|=|E_1| となる G_2、V ⊆ V_2 の頂点のサブセット、および G_2 のエッジのサブセット、E ⊆ E_2 があり、1 対{u,v} ∈ E_1 <=> { f(u),f(v) } ∈ E) となる、G_2 の頂点 V のサブセットでの G_1 の頂点の 1 つの一致、f:V_1 -> V
- 問題のサブグラフ同型が NP に属することを示します。
- 問題が NP 完全であることを示し、問題の Clique をそれに還元します。(ヒント: グラフ G_1 が完成していると考えてください)
私は次のことを試しました：
- 非決定論的チューリング マシンは、最初にノード V のサブセットと G_2 のエッジ E のサブセットを「推測」し、その後、|V|=|V_1| であることを検証します。および |E|=|E_1| {u,v} ∈ E_1 <=> { f(u), f(v) } ∈ E となるような 1 対 1 の対応 f: V_1 -> V があること。
O(|V_2|^2) 個の異なる頂点のペアがあるため、チェックには多項式時間が必要です。したがって、問題は NP に属します。
- (G,k) をクリーク問題の任意のインスタンスとします。ここで、k はクリークの頂点の数です。
サブグラフ同型問題のインスタンスを多項式時間で次のように構成できます。 G_2 は n 頂点上のグラフです。
G_1 は、いくつかの k <= n について、k 個の頂点の完全なグラフです。G=G_2 とします。問題 Subgraph Isomorphism には、G_2 に k 個の頂点を持つ完全な部分グラフがある場合、つまり、グラフ G に k 個の頂点を持つ完全な部分グラフがある場合に解があります。
したがって、問題 Clique の最初のインスタンスに解がある場合、Subgraph Isomorphism の問題のインスタンスには解があります。
したがって、Subgraph Isomorphism の問題は NP 完全です。
それが正しいかどうか、または何か改善できるかどうか教えていただけますか?