# How to prove this isomorphism-related graph problem is NP-complete?

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.

-

## migrated from cstheory.stackexchange.comJan 16 '13 at 15:37

This question came from our site for theoretical computer scientists and researchers in related fields.

What have you tried? Do you know how one usually proves that a problem is NP-complete? –  Yuval Filmus Jan 16 '13 at 13:08
I have to find another NP-complete problem and reduce it to this one, but I cannot think of a way to transform this problem into another problem. –  Charlie Jan 16 '13 at 13:11
Good thing you don't have to: you have to transform instances of the other problem into ones of this problem. –  Raphael Jan 16 '13 at 15:48

## 2 Answers

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.

-
I do not think that there are many versions of subgraph isomorphism problem. The subgraph isomorphism problem is exactly the one you described: given graphs G_1 and G_2, decide whether G_1 contains a subgraph that is isomorphic to G_2. And this is different from the problem stated in the question. In the problem stated in the question, the task is to decide whether G_1 contains an induced subgraph that is isomorphic to G_2. –  Tsuyoshi Ito Jan 29 '13 at 3:48