1
$\begingroup$

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).

Improve this question
$\endgroup$
8
  • $\begingroup$ Well, what happens if you choose $G$ to be a clique with $k$ vertices? $\endgroup$
    – dkaeae
    Mar 11, 2019 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$
    – DanGoodrick
    Mar 11, 2019 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$
    – David Richerby
    Mar 11, 2019 at 16:35
  • 3
    $\begingroup$ Possible duplicate of Subgraph isomorphism reduction from the Clique problem $\endgroup$
    – David Richerby
    Mar 11, 2019 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$
    – DanGoodrick
    Mar 13, 2019 at 12:01

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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$
    – DanGoodrick
    Mar 11, 2019 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$
    – David Richerby
    Mar 11, 2019 at 16:36
  • $\begingroup$ I thought H could be any graph, not just a graph that is isomorphic to G. $\endgroup$
    – DanGoodrick
    Mar 13, 2019 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$
    – David Richerby
    Mar 13, 2019 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$
    – DanGoodrick
    Mar 13, 2019 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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