Maximum common induced subgraph
In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.
Finding this graph is NP-hard. In the associated decision problem, the input is two graphs G and H and a number k. The problem is to decide whether G and H have a common induced subgraph with at least k vertices. This problem is NP-complete.[1] It is a generalization of the induced subgraph isomorphism problem, which arises when k equals the number of vertices in the smaller of G and H, so that this entire graph must appear as an induced subgraph of the other graph.
One possible solution for this problem is to build a modular product graph of G and H. In this graph, the largest clique corresponds to a maximum common induced subgraph of G and H. Therefore, algorithms for finding maximum cliques can be used to find the maximum common induced subgraph.[2]
Maximum common induced subgraph algorithms have a long tradition in cheminformatics and pharmacophore mapping.[3]
See also
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.
- ^ Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
- ^ Raymond, John W.; Willett, Peter (2002), "Maximum common subgraph isomorphism algorithms for the matching of chemical structures", Journal of Computer-Aided Molecular Design, 16 (7): 521–533, doi:10.1023/A:1021271615909.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |