Maximum common subgraph isomorphism problem
Encyclopedia
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)
The associated decision problem
, i.e., given G1, G2 and an integer k, deciding whether G1 contains an induced subgraph of at least k edges isomorphic to an induced 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
.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, maximum common subgraph-isomorphism (MCS) is an optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
that is known to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. The formal description of the problem is as follows:
Maximum common subgraph-isomorphism(G1, G2)
- Input: Two graphGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
s G1 and G2. - Question: What is the largest induced subgraph of G1 isomorphic to an induced subgraph of G2?
The associated decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
, i.e., given G1, G2 and an integer k, deciding whether G1 contains an induced subgraph of at least k edges isomorphic to an induced subgraph of G2 is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
.
One possible solution for this problem is to build a modular product graph
Modular product of graphs
In graph theory, the modular product of graphs G and H is a graph such that* the vertex set of the modular product of G and H is the cartesian product V × V; and...
, in which the largest clique
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
represents a solution for the MCS problem.
MCS algorithms have a long tradition in cheminformatics
Cheminformatics
Cheminformatics is the use of computer and informational techniques, applied to a range of problems in the field of chemistry. These in silico techniques are used in pharmaceutical companies in the process of drug discovery...
and pharmacophore mapping
Pharmacophore
thumb|right|300px|An example of a pharmacophore model.A pharmacophore is an abstract description of molecular features which are necessary for molecular recognition of a ligand by a biological macromolecule....
.