Next: MAXIMUM COMMON INDUCED SUBGRAPH Up: Iso- and Other Morphisms Previous: Iso- and Other Morphisms Index

### MAXIMUM COMMON SUBGRAPH

- INSTANCE: Graphs and .

- SOLUTION: A common subgraph, i.e. subsets and such that the two subgraphs and are isomorphic.

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

- Bad News: APX-hard [208].

- Comment: Transformation from MAXIMUM CUT. Not approximable with an absolute error guarantee of for some [433]. Transformation to MAXIMUM CLIQUE with a quadratic vertex amplification [267]. Variation in which the degree of the graphs G1 and G2 is bounded by the constant B is not harder to approximate than the bounded degree induced common subgraph problem and is approximable within B+1 [266].

- Garey and Johnson: GT49