237 views

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?

(i) $L \in NP$.

(ii) $L$ is $NP$- hard.

(iii) $L$ is undecidable.

1. Only $(i)$
2. Only $(ii)$
3. Only $(iii)$
4. $(i)$ and $(ii)$
5. $(ii)$ and $(iii)$
| 237 views

+1 vote
graph isomporphism is np complete  and decidable so ans is d
by Boss (31.4k points)
+1

It is known to be one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known.The problem is neither known to be solvable in polynomial time nor NP-complete,

But the question asks about Subgrpah Isomorphism which is NP complete(both NP and NP-Hard).

https://en.wikipedia.org/wiki/Graph_isomorphism

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.

by Veteran (119k points)