<p>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'$.</p>

<p><em>Proof</em>: 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'$. <em>Q.E.D.</em></p>

<p>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].</p>

<ol>
<li>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</li>
<li>M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.</li>
<li>V. Kann. On the Approximability of NP-complete Optimization Problems. Ph.D. Thesis, NADA report TRITA-NA-9206, 1992. <a href="http://www.nada.kth.se/~viggo/papers/phdthesis.pdf" rel="nofollow">http://www.nada.kth.se/~viggo/papers/phdthesis.pdf</a></li>
</ol>

CC BY-SA 3.0
2012-06-04T16:45:50.570Z
It looks like this is indeed equivalent to my problem. Thanks a lot! Are you aware of results on a weighted version of Max CES?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-06-04T23:17:19.500Z
I have no idea on weighted version. I think $\max_{v_1,v_2} \max (\ldots)$ should be $\sum_{v_1,v_2} \max (\ldots)$, right?
Yota Otachi
CC BY-SA 3.0
2012-06-05T12:07:07.280Z
Yes, the sum is more natural if we want to generalize the unweighted case, though I guess it could make sense to minimize the sum of squares or any function of the weight difference.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-06-05T13:02:30.317Z
Thanks for editing. I agree, it's natural to use the sum of weight differences (or any function on it) as penalty.
Yota Otachi
CC BY-SA 3.0
2012-06-04T15:03:16.953Z
2012-06-04T23:04:03.763Z
2012-06-04T23:04:03.763Z
Yota Otachi
<p>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 <a href="https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem" rel="nofollow">subgraph isomorphism problem</a> 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.</p>

<p>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).</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-05-30T23:16:34.757Z
Why do you need "induced" in the title?
Yota Otachi
CC BY-SA 3.0
2012-05-30T23:38:03.023Z
@Yota Otachi: Because I messed up. Thanks!
Antoine Amarilli 'a3nm'
<cc.complexity-theory><ds.algorithms><graph-theory><approximation-algorithms><graph-isomorphism>
Imperfect subgraph isomorphism
Antoine Amarilli 'a3nm'
# Imperfect subgraph isomorphism

(Asked by: username_0 on 2012-05-30)

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](https://en.wikipedia.org/wiki/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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, approximation-algorithms, graph-isomorphism

> **Comments:**
> **username_1**: Why do you need "induced" in the title?  
> **username_0**: @username_1: Because I messed up. Thanks!  

---

## 1 answers

### Answer by username_1 on 2012-06-04. Score: 7 | Accepted answer

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].

1. 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
2. M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.
3. 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>

> **Comments:**
> **username_0**: It looks like this is indeed equivalent to my problem. Thanks a lot! Are you aware of results on a weighted version of Max CES?  
> **username_1**: I have no idea on weighted version. I think $\max_{v_1,v_2} \max (\ldots)$ should be $\sum_{v_1,v_2} \max (\ldots)$, right?  
> **username_0**: Yes, the sum is more natural if we want to generalize the unweighted case, though I guess it could make sense to minimize the sum of squares or any function of the weight difference.  
> **username_1**: Thanks for editing. I agree, it's natural to use the sum of weight differences (or any function on it) as penalty.  

---

