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.

  • 1
    $\begingroup$ What have you tried? Do you know how one usually proves that a problem is NP-complete? $\endgroup$ Jan 16, 2013 at 13:08
  • $\begingroup$ 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. $\endgroup$
    – Charlie
    Jan 16, 2013 at 13:11
  • 3
    $\begingroup$ Good thing you don't have to: you have to transform instances of the other problem into ones of this problem. $\endgroup$
    – Raphael
    Jan 16, 2013 at 15:48

2 Answers 2


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.

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 29, 2013 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.