MHB Is the Subgraph Isomorphism problem NP-complete?

[evinda]

Hello! (Wave)Subgraph isomorphism

We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$.

Question: Is the graph $G_1$ isomorphic to a subgraph of $G_2$ ?
(i.e. is there a subset of vertices of $G_2, V \subseteq V_2$ and subset of the edges of $G_2, E \subseteq E_2$ such that $|V|=|V_1|$ and $|E|=|E_1|$ and is there a one-to-one matching of the vertices of $G_1$ at the subset of vertices $V$ of $G_2, f:V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u),f(v) \} \in E$)

• Show that the problem Subgraph isomorphism belongs to NP.
• Show that the problem is NP-complete reducing the problem Clique to it. (Hint: consider that the graph $G_1$ is complete)

I have tried the following:

• A non-deterministic Turing machine first "guesses" the subset of nodes $V$ and the subset of edges $E$ of $G_2$ and after that it verifies that $|V|=|V_1|$ and $|E|=|E_1|$ and that there is a one-to-one correspondence $f: V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u), f(v) \} \in E $.
  Since there are $O(|V_2|^2)$ different pairs of vertices, the check requires polynomial time. So the problem belongs to NP.
• Let $(G,k)$ an arbitrary instance of the clique problem, where $k$ is the number of vertices of the clique.
  We can construct an instance of the Subgraph isomorphism problem in polynomial time as follows:
  $G_2$ is a graph on $n$ vertices.
  $G_1$ is a complete graph on $k$ vertices, for some $k \leq n$.
  Let $G=G_2$.
  The problem Subgraph Isomorphism has a solution iff there is a complete subgraph of $G_2$ with $k$ vertices, i.e. iff the graph $G$ has a complete subgraph with $k$ vertices.
  Thus, the instance of the problem Subgraph Isomorphism has a solution iff the initial instance of the problem Clique has a solution.
  Therefore, the problem Subgraph Isomorphism is NP-complete.

Could you tell me if it is right and if I could improve something?

 

[evinda]

Would it be better to say the following for the second part?

Let $(G,k)$ be an arbitrary instance of the clique problem, where $k$ is the number of vertices of the clique.
We can construct an instance of the Subgraph Isomorphism problem in polynomial time as follows:
$G_1$ is a complete graph with $k$ vertices.
Let $G_2=G$.
The graph $G_1$ is isomorphic to a subgraph of $G_2$ iff there is a complete subgraph of $G_2$ with $k$ vertices, i.e. iff $G$ has a complete subgraph with $k$ vertices.
Thus the instance of the Subgraph Isomorphism problem has a solution iff the initial instance of the problem clique has a solution.
Since the clique problem that is NP-complete can be reduced to the Subgraph Isomorphism problem, we can deduce that the latter is NP-complete.