The subgraph-isomorphism problem takes two undirected graphs G1 and G2, andit asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.

To show that the subgraph-isomorphism problem is NP-complete, we need to demonstrate two things:

1. The problem is in NP.
2. The problem is NP-hard.

Step 1: The problem is in NP

To show that the subgraph-isomorphism problem is in NP, we need to demonstrate that a given solution can be verified in polynomial time. Given two graphs $G1$ and $G2$, and a mapping $f$ from the vertices of $G1$ to the vertices of $G2$, we can verify whether $f$ is an isomorphism from $G1$ to a subgraph of $G2$ in polynomial time by checking the following conditions:

• $f$ is a bijection between the vertices of $G1$ and a subset of the vertices of $G2$.
• For every edge $(u, v)$ in $G1$, there is an edge $(f(u), f(v))$ in $G2$.

Both of these checks can be done in polynomial time, so the subgraph-isomorphism problem is in NP.

Step 2: The problem is NP-hard

To show that the subgraph-isomorphism problem is NP-hard, we need to reduce a known NP-hard problem to it in polynomial time. We will use the clique problem, which is known to be NP-hard.

The clique problem asks whether a given graph $G$ contains a complete subgraph (clique) of size $k$. We will reduce this problem to the subgraph-isomorphism problem.

Given an instance of the clique problem, i.e., a graph $G$ and an integer $k$, we construct an instance of the subgraph-isomorphism problem as follows:

• Let $G1$ be the complete graph $K_k$ on $k$ vertices.
• Let $G2$ be the graph $G$.

We need to determine whether $G1$ (the complete graph on $k$ vertices) is isomorphic to a subgraph of $G2$. If $G$ contains a clique of size $k$, then there exists a subgraph of $G$ that is isomorphic to $K_k$. Conversely, if $G1$ is isomorphic to a subgraph of $G2$, then $G$ contains a clique of size $k$.

This reduction can be done in polynomial time, and since the clique problem is NP-hard, the subgraph-isomorphism problem is also NP-hard.

Conclusion

Since we have shown that the subgraph-isomorphism problem is in NP and is NP-hard, we can conclude that the subgraph-isomorphism problem is NP-complete.