Question

Design & Analysis of Algorithms

Problem 3. 34.5-1 to prove the subgraph-isomorphism problem is NP-complete.

Answer 1

Question: Show that the subgraph-isomorphism problem is NP-complete

We consider two undirected graph G1 and G2 and it asks weather G1 is isomorphic to subgraph go G2.

Proof:

To demonstrate that it is a NP-complete, we can see that there us a mapping (φ) structure hub of G1 to hub of G2, which is being depicted as vertices of G2 comparing to the vertices of G1. This should be ensure that each edge E=(x,y) in G1, so the edge will be (φ(x),φ(y)) is additionally in G2, and at whatever point the edge E=(x,y) isn't an edge of the G1, at that point (φ(x),φ(y)) isn't an edge of G2. This can be with the assistance of only two straightforward settled circles, and it takes nearly O(n2) time.

So to demonstrate NP-hardness,we can demonstrate that for an occurrence, coterie issue is an uncommon case in this. As given the case of club, diagram G and the number N, we can produce an occasion of subgraph-isomorphism by putting the incentive as G2=G and G1 as a Clique of the N vertices. This decrease takes O(N2) time.

To demonstrate the rightness of the decrease, initially given us a chance to expect that the G contains an inner circle of size N. From that point onward, these N hubs of the G=G2 are isomorphic to G1, in light of the fact that as we realize that G1 is an inner circle of size N.

The other way around, If G2 contain a subgraph-isomorphic to the G1, in light of the fact that as G1 is a N inner circle and G2 must contain a N-coterie.

Consequently, we can say that (G,N) is subgraph-isomorphism for this occasion.