Subgraph isomorphism problem

In computational complexity, the subgraph isomorphism problem, also sometimes called subgraph matching problem, is an NP-complete decision problem, which is formally defined as follows:

The NP-completeness of the problem is demonstrated by reducing this problem to the Click Problem. If the subgraph isomorphism problem was polynomial, it could be used to solve the Click Problem, also in polynomial time. Let n be the number of edges of G, we can execute the problem of isomorphism of subgraphs n-2 times (G1 being a clique of size 3 to n, and G2 being G) to find the largest clique in G. This problem is a generalization of the possibly simplest problem of graph isomorphism, in the sense that if the latter is NP-complete, then the polynomial hierarchy collapses, so it is not supposed to be so.

wiki