Next: MAXIMUM COMMON EMBEDDED SUB-TREE Up: Iso- and Other Morphisms Previous: MAXIMUM COMMON SUBGRAPH Index

### MAXIMUM COMMON INDUCED SUBGRAPH

- INSTANCE: Graphs and .

- SOLUTION: A common induced subgraph, i.e. subsets and such that |V1'|=|V2'|, and the subgraph of G1 induced by V1' and the subgraph of G2 induced by V2' are isomorphic.

- MEASURE: Cardinality of the common induced subgraph, i.e., |V1'|.

- Bad News: Not approximable within for some [266].

- Comment: Transformations to and from MAXIMUM CLIQUE. Variation in which the degree of the graphs G1 and G2 is bounded by the constant B is APX-hard and is approximable within B+1. If the induced subgraph is restricted to be connected the problem is NPO PB-complete and not approximable within for any [266].