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. 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.
Based on hardness of approximation results for the maximum independent set problem, the maximum common induced subgraph problem is also hard to approximate. This implies that, unless P = NP, there is no approximation algorithm that, in polynomial time on -vertex graphs, always finds a solution within a factor of of optimal, for any.
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.
Maximum common induced subgraph algorithms have a long tradition in cheminformatics and pharmacophore mapping.
