Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jan 16 '13 at 15:37

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

1  
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
3  
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 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.

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.