Subgraph Isomorphism problem

題目

1. SIP 屬於 NP

給定一個 Certificate : 令 G = (V, E) 為 G2 的一個子圖，且我們知道 G1 = (V', E') 和 G 的對應方式。
驗證 : 我們需要去檢查 G1 是否和 G 同構。(1) 檢查對應方式是不是 Bijection (2) 驗證每個在 G1 的邊 (u, v) 是否也有一個對應在 G 的邊 (f(u), f(v))；不在 G 的邊也一定不會在 G2 中出現，而這需要花 \(O(V^2)\) 時間。因此 SIP 可在多項式時間內驗證，故 SIP 屬於 NP。

2. SIP 屬於 NP-Hard

此問題可以將決策版 CLIQUE 問題轉成 SIP
K-CLIQUE : 給定一圖 G 問是否存在一個大小為 K 的完全子圖。
SIP : 給定兩圖 G1, G2 問 G1 是否和 G2 的子圖同構。(白話文 : G2 中是否可以找到 G1)

假設給定一圖 G，節點數為 n，並把 G1 設定成一個大小為 k 的完全子圖，G2 設定成 G。
給定一個 CLIQUE 問題的輸入 (G, k)，問圖 G 中是否存在一個 k-clique，則如上述設定方式可將此問題轉成 SIP 為「 G1 = k-clique 是否和 G2 = G 的子圖同構」。因此，在 CLIQUE 問題中若 G 中確實存在一個 k-clique，則在 SIP 問題中就代表 k-clique 和 G 的某個子圖同構；反之，若 k-clique 和 G 的某個子圖同構，則在 CLIQUE 問題中 G 中一定存在一個 k-clique。
\[CLIQUE(G, k) \Longleftrightarrow SIP(k-clique, G)\]轉換時間就是建造 G1 的時間 = \(O(k^2) = O(n^2)，因為\ k\le n\)，故可將決策版 CLIQUE 問題在多項式時間內轉成 SIP，又決策版 CLIQUE 問題屬於 NPC，所以 SIP 屬於 NP-hard。

總結 (1)(2) 最後可得證 SIP 屬於 NPC。

註 : 若 \(k > n\)，則 CLIQUE(G, k) 不存在，SIP(k-clique, G) 也為 Falue