Prove that Sub Graph Isomorphism is Hard

Question

SI: Given graphs G, H: does graph G contain graph H as a subgraph?

Prove that this decision problem is NP-complete.

Answer 1

First, observe that subgroup isomorphism is in NP, because if we are given a specification of the subgraph of G and the mapping between its vertices and the vertices of H, we can verify in polynomial time that H is indeed isomorphic to the specified subgraph of G. 

To show subgraph isomorphism is NP-hard, we reduce from clique. Given an instance (G, k) of clique, where G has n vertices, we produce the following instance of subgraph isomorphism: (G, H = K_l), where K_l is the complete graph on l vertices and l = min(k, n+ 1). This reduction runs in polynomial time. 

If k > n, then (G, k) is a no instance of clique and by our choice of l we produce a no instance of subgraph isomorphism, since there can be no Kn+1 graph within G which has only n vertices. Otherwise, it is clear that G contains a clique of size l = k if and only if G contains a subgraph isomorphic to H (these are just two ways of saying the same thing). Thus we have shown that subgraph isomorphism is NP-hard, as desired.

Answer 2

As the certificate uses the one-to-one function f from the vertices of H to the vertices

of G. Thus the length of the certificate is O(n). Finally, given the certificate the

verification algorithm can confirm that f is a one-to-one function and then take each

edge (u,v) belongs to H and verify that (f (u),f (v)) belongs to G. Clearly this can be done in O(n+m) time. We now prove that CLIQUE <= p subgraph-isomorphism.

Let <G,k> be the input for clique. For the subgraph-isomorphism input, we let H

be a complete graph on k vertices. Clearly this can be done in polynomial time. To see this notice that we can assume that k <=n (or otherwise, clearly G does not have a clique of size k) and thus the time to create H is simply O(k^2) = O(n^2) which is polynomial in the number of bits to represent G.

By definition of a clique being a complete graph on k vertices, there is a clique of

size k in G if and only if H is a subgraph of G. That is if there is a clique of k

vertices in G then mapping the vertices of H to those vertices in G gives a solution

for the subgraph isomorphism problem. Similarly, if there is a solution to the subgraph isomorphism problem, then the vertices in G mapped to by the vertices in H form a clique of k vertices.

Answer 3

To prove the decision version of whether a graph has a subgraph we will show a reduction from Clique to this Subgraph problem, I will call this problem SbG.

Hence for a NP-complete reduction we would first have to prove that SbG is in NP. We can verify in polynomial time that H is indeed a subgraph in G, this is trivial as if we have the <K,E`> we can check whether Graph G indeed has those vertices and edge pairs by traversing those specific edges and vertices in G.

Given the <K,E`> in graph H, and <V,E> in graph G. Let us assume H is complete graph with K vertices if and only if G has a Clique sized K. We can see that since H is a complete graph on K vertices a Clique with size K in the overall graph G would be this complete graph with exactly K vertices. Hence SbG is at least as hard as the Clique problem, Clique <_p SbG

*I can not add images otherwise I would draw the box as well