GT42 M AXIMUM C OMMON S UBGRAPH

       
• I NSTANCE : Graphs and .
• S OLUTION : A common subgraph, i.e. subsets and such that the two subgraphs and are isomorphic.
• M EASURE : Cardinality of the common subgraph, i.e., |E'| .

• Bad News: A PX -hard [ 150 ].
• Comment: Transformation from M AXIMUM C UT . Not approximable within an absolute error guarantee of for some [ 336 ]. Transformation to M AXIMUM C LIQUE with a quadratic vertex amplification [ 200 ]. 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 [ 199 ].
• Garey and Johnson: GT49