Maximum common subgraph isomorphism problem

From Wikipedia, the free encyclopedia

In complexity theory, Maximum Common Subgraph-Isomorphism (MCS) is an optimization problem that is known to be NP-complete. The formal description of the problem is as follows.

Maximum Common Subgraph-Isomorphism(G₁, G₂)
Input: Two graphs G₁ and G₂.
Question: What is the largest subgraph of G₁ isomorphic to a subgraph of G₂?

One possible solution for this problem is to build a product graph, in which the largest clique represents a solution for the MCS problem.

MCS algorithms have a long tradition in Cheminformatics and pharmacophore mapping.

[edit] See also

• Graph isomorphism problem
• Subgraph isomorphism problem
• Molecule mining

[edit] References

• 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.