My watch list
my.chemeurope.com

# Subgraph isomorphism problem

In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.

Subgraph-Isomorphism(G1, G2)
Input: Two graphs G1 and G2.
Question: Is G1 isomorphic to a subgraph of G2?

Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.

The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem. If subgraph isomorphism were polynomial, you could use it to solve the clique problem in polynomial time. Let n be the number of edges in G: you can then run the subgraph isomorphism n-2 times (with G1 being a clique of size 3 to n, and G2 being G) to find the largest clique in G.

Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.

### Application areas

In the area of cheminformatics often the term substructure search is used. Typically a query structure is defined as SMARTS, a SMILES extension.

Also of main importance to graph grammars.