- INSTANCE:
Graphs
and
.
- SOLUTION:
A common induced subgraph, i.e. subsets
and
such that
,
and the subgraph of
induced by
and the subgraph of
induced by
are isomorphic.
- MEASURE:
Cardinality of the common induced subgraph, i.e., .

*Bad News:*Not approximable within for some [281].*Comment:*Transformations to and from MAXIMUM CLIQUE. Variation in which the degree of the graphs and 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 [281].