- #1
evinda
Gold Member
MHB
- 3,836
- 0
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$)
Could you tell me if it is right and if I could improve something?
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)
- 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?