- 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., .

*Bad News:*APX-hard [221].*Comment:*Transformation from MAXIMUM CUT. Not approximable with an absolute error guarantee of for some [456]. Transformation to MAXIMUM CLIQUE with a quadratic vertex amplification [282]. Variation in which the degree of the graphs and 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*[281].*Garey and Johnson:*GT49