edited by
973 views
5 votes
5 votes

Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the following language.

$L=\{(G, H)| G$ and $H$ are undirected graphs such that a subgraph of $G$ is isomorphic to $H\}$

Then which of the following are true?

  1. $L \in NP$.
  2. $L$ is $NP$- hard.
  3. $L$ is undecidable.

 

  1. Only $(i)$
  2. Only $(ii)$
  3. Only $(iii)$
  4. $(i)$ and $(ii)$
  5. $(ii)$ and $(iii)$
edited by

2 Answers

1 votes
1 votes
graph isomporphism is np complete  and decidable so ans is d
0 votes
0 votes

The graph isomorphism is not NP Complete, but the isomorphism of subgraph of a graph is NP Hard , as well as NP Complete. Now,if a decision problem is NP Hard as well as NP Complete, then we can say it is also in NP

Notice that this problem is different from Graph Isomorphism: in the latter, you are given two graphsG1,G2 (presumably of the same size), and are to decide if the two are isomorphic. Graph Isomorphism is rather famous for the fact that neither is it known to be NP-complete (most researchers believe that is rather unlikely), nor does anyone have a polynomial-time algorithm. Subgraph Isomorphism, on the other hand, is known to be NP-complete, and we will prove that here.

To see that the problem is in NP, we observe that a certificate is a mapping φ from the nodes of G1 to (a subset of) the nodes of G2, describing which vertices of G2 correspond to vertices of G1. The certifier then needs to make sure that for each edge e = (u,v) in G1, the edge (φ(u),φ(v)) is also in G2, and whenever (u,v) is not an edge of G1, then (φ(u),φ(v)) is not an edge of G2. This can be done with two simple nested loops, and takes at most O(n2) time, i.e., polynomial.

To prove NP-hardness, we show that, for instance, the Clique problem is a special case. Given an instance of Clique, consisting of a graph G and a number k, we generate an instance of Subgraph Isomorphism by setting G2 = G, and G1 a clique on k vertices. This reduction clearly takes polynomial time, since all we do is copy a graph, and write down a complete graph in time O(k2).

To prove correctness of the reduction, first assume that G contains a clique of size k. Then, those k nodes of G = G2 are isomorphic to G1, because G1 is a clique of size k.

Conversely, if G2 contains a subgraph isomorphic to G1, because G1 is a k-clique, G2 must contain ak-clique. Thus, (G, k) is a “Yes” instance.

http://web.mit.edu/bmhuang/www/notes/18404-notes.pdf 

Answer:

Related questions

20 votes
20 votes
2 answers
1
28 votes
28 votes
7 answers
2
2 votes
2 votes
2 answers
3
makhdoom ghaya asked Jun 27, 2016
3,418 views
Consider the graph given below as :Which one of the following graph is isomorphic to the above graph ?
42 votes
42 votes
6 answers
4
go_editor asked Sep 28, 2014
17,332 views
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.