MINIMUM GRAPH TRANSFORMATION

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

• SOLUTION: A transformation that makes $G_1$ isomorphic to $G_2$. In the transformation a set of edges $E'\subseteq E_1$ is removed from $E_1$ and added to $E_2$.

• MEASURE: Cardinality of the transformation set, i.e., $\vert E'\vert$.

  
  

• Bad News: APX-hard [359].

• Comment: Transformation from MAXIMUM 3-SATISFIABILITY.