Imperfect subgraph isomorphism Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges $(v_1, v_2) \in E$ such that $(f(v_1), f(v_2)) \notin E'$. This is a generalization of the subgraph isomorphism problem where we allow the subgraphs to be isomorphic up to a few missing edges and want to find the way to minimize the number of missing edges.

I would also be interested in the weighted version of this problem, where vertex couples $(v_1, v_2) \in V^2$ carry a weight $w(v_1, v_2)$ (which must be zero if $(v_1, v_2) \notin E)$, and likewise for $G'$, and we wish to minimize $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ (the $\max$ is there to only penalize weights from the query graph being larger than those of the reference graph).

My question are: Has this problem already been studied? Does it have a well-known name? Are there any efficient approximation algorithms known? 

The motivation of this problem (apart from the fact that it seems like a natural generalization of the subgraph isomorphism problem) is that it is a nice way to make a table plan for a party: the query graph is the graph of guests with edge weights representing the extent to which two people want to interact, the reference graph has the table seats as vertices and edge weights indicating to what extent communication is possible, the solution of the problem is a mapping from people to table seats which respects the social structure to the fullest possible extent.
Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows:
given two graphs $G$ and $G'$, find a graph $H$ with the maximum number of edges
that is isomorphic to a subgraph of $G$ and to a subgraph of $G'$.

Proof: You are finding a subgraph $H$ of $G$ isomorphic to a subgraph of $G'$,
where $|E_{G}| - |E_{H}|$ is minimized. Since $|E_{G}|$ is an invariant of $G$,
$|E_{G}| - |E_{H}|$ is minimized if and only if $|E_{H}|$ is maximized.
Clearly, $H$ is isomorphic to a subgraph of $G$ and to a subgraph of $G'$. Q.E.D.

Approximability. In the Ph.D thesis of Kann, I found the description
"not known to be approximable within a constant" [3] (p. 115).
In a recent paper by Bahiense et al. [1],
it is mentioned that if $|V_{G}|$ and $|V_{G'}|$ are not required to be equal,
the problem becomes APX-hard.
But the citation for this result is an unpublished private communication [2].


L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, to appear. doi:10.1016/j.dam.2012.01.026
M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.
V. Kann. On the Approximability of NP-complete Optimization Problems. Ph.D. Thesis, NADA report TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf