Question: Given 2 undirected graphs $G_1$, $G_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H_2$ of $G_2$. What is the lowest complexity class for this problem: a. PSPACE b. NPC c. NP d. P
Thoughts We were thinking of this to be in NP because we can get a certificate of such two subgraphs and check the in polynomial time. But - we cannot determine whether this is complete or not. Is the only way to determine that is by trying to find a reduction to an NPC problem? Is there a specific way to prove that a language is NOT NPC but in NP?