My watch list  

Maximum common subgraph isomorphism problem

In complexity theory, maximum common subgraph-isomorphism (MCS) is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:

Maximum common subgraph-isomorphism(G1, G2)

  • Input: Two graphs G1 and G2.
  • Question: What is the largest induced subgraph of G1 isomorphic to a subgraph of G2?

The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k edges isomorphic to a subgraph of G2 is NP-complete.

One possible solution for this problem is to build a modular 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.

See also


  • 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.
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Maximum_common_subgraph_isomorphism_problem". A list of authors is available in Wikipedia.
Your browser is not current. Microsoft Internet Explorer 6.0 does not support some functions on Chemie.DE