|
Consider the following problem: Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ and some non-negative integer $k \in \mathbb{N}$, is it possible to delete at most $k$ vertices from $G_1$ to obtain $G_1'$ such that $G_1' \cong G_2$, i.e. the resulting graph is isomorphic to $G_2$. I have to show that this problem is NP-complete. Can somebody help me with this problem? It is school homework and I don't know how to solve it. |
|||||||||
|
|
Here's a hint: Consider Vertex Cover, which is NP-complete. If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices. Edit: The correct reduction (by using Vertex Cover) shows the problem to be NP-hard. Given the correct witnesses, you can easily show that it is in NP. |
||||
|
|
|
Your problem is one version of famous subgraph isomorphism problem which is NP-complete. It is a computational task in which two graphs G and H are given as inputs, and one must determine whether G contains a subgraph that is isomorphic to H. There are many solutions on the web for this problem. |
|||||
|
