GT43 M AXIMUM C OMMON I NDUCED S UBGRAPH

         
• I NSTANCE : Graphs and .
• S OLUTION : A common induced subgraph, i.e. subsets and such that , and the subgraph of induced by and the subgraph of induced by are isomorphic.
• M EASURE : Cardinality of the common induced subgraph, i.e., .

• Bad News: Not approximable within for some [ 199 ].
• Comment: Transformations to and from M AXIMUM C LIQUE . Variation in which the degree of the graphs and is bounded by the constant B is A PX -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 [ 199 ].