Subgraph isomorphism problem

From Wikipedia, the free encyclopedia

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(G₁, G₂)
Input: Two graphs G₁ and G₂.
Question: Is G₁ isomorphic to a subgraph of G₂?

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 G₁ being a clique of size 3 to n, and G₂ 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.

[edit] 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.

[edit] See also

• Induced subgraph isomorphism problem
• Maximum common subgraph isomorphism problem

[edit] References

• J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.4: GT48, pg.202.