MAXIMUM COMMON SUBGRAPH

• INSTANCE: Graphs $G_1=\left(V_1,E_1\right)$ and $G_2=\left(V_2,E_2\right)$.

• SOLUTION: A common subgraph, i.e. subsets ${E_1}'\subseteq E_1$ and ${E_2}'\subseteq E_2$ such that the two subgraphs $G_1'=\left(V_1,{E_1}'\right)$ and $G_2'=\left(V_2,{E_2}'\right)$ are isomorphic.

• MEASURE: Cardinality of the common subgraph, i.e., $\vert E'\vert$.

  
  

• Bad News: APX-hard [221].

• Comment: Transformation from MAXIMUM CUT. Not approximable with an absolute error guarantee of $\min(\vert V_1\vert,\vert V_2\vert)^{\varepsilon }$ for some $\varepsilon >0$ [456]. Transformation to MAXIMUM CLIQUE with a quadratic vertex amplification [282]. Variation in which the degree of the graphs $G_1$ and $G_2$ 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