I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link that demonstrates how Subgraph Isomorphism reduces to CLIQUE, but I can't figure out how to reverse it. Subgraph isomorphism reduction from the Clique problem

Here is a formal example of the problem from DASGUPTA 8.10: Given as input two undirected graphs G and H, determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).

  • $\begingroup$ Well, what happens if you choose $G$ to be a clique with $k$ vertices? $\endgroup$
    – dkaeae
    Mar 11 '19 at 16:18
  • $\begingroup$ Can you do that? If so, that is the answer because a clique will contain every possible subgraph of size k. But is it legal to constrain the input to a specific G that is fully connected? I thought it had to take any graphs G and H $\endgroup$ Mar 11 '19 at 16:20
  • $\begingroup$ The question you link actually shows that clique reduces to subgraph isomorphism, which is the exact thing you're looking for. $\endgroup$ Mar 11 '19 at 16:35
  • 3
    $\begingroup$ Possible duplicate of Subgraph isomorphism reduction from the Clique problem $\endgroup$ Mar 11 '19 at 16:35
  • $\begingroup$ The link I provided assumes a fully connected graph but my question only specifies any graph H. Is the reduction still possible/valid in this case? $\endgroup$ Mar 13 '19 at 12:01

A subgraph is isomorphic to a clique if, and only if, it is a clique.

  • $\begingroup$ But what if H doesn't have a clique the same size as G? There are lots of permutations of H that may or may not be isomorphic with G. $\endgroup$ Mar 11 '19 at 16:23
  • $\begingroup$ I'm not sure what you mean. If H is isomorphic to G, any permutation of H is also isomorphic. $\endgroup$ Mar 11 '19 at 16:36
  • $\begingroup$ I thought H could be any graph, not just a graph that is isomorphic to G. $\endgroup$ Mar 13 '19 at 11:58
  • $\begingroup$ We're trying to reduce $k$-clique to sub graph isomorphism. That means we're given a graph $F$ and a number $k$, and we need to produce graphs $G$ and $H$ such that $G$ has a subgraph isomorphic to $H$ if, and only if, $F$ has a clique of size at least $k$. We get to choose the input to subgraph isomorphism. $\endgroup$ Mar 13 '19 at 12:42
  • $\begingroup$ Thanks for addressing my concern. So in my other reduction exercises, I have taken the input to a known NP Complete problem, modified it, and produced the same answer as the known NPC but with a unproven NP Complete problem. For example, I took the input for SAT (known NPC) and modified it to be a valid input for 3SAT. Then I modified the output of 3SAT to give the same result as would have been obtained by SAT. So, that is what I know how to do. This seems to be a different problem. A cascade of sorts. Am I correct in my understanding? $\endgroup$ Mar 13 '19 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.