<p>From the paper <a href="http://link.springer.com/chapter/10.1007/978-3-642-32589-2_12">Approximate Graph Isomorphism</a>:</p>

<blockquote>
  <p>We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $π$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α &lt; 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.</p>
</blockquote>

CC BY-SA 3.0
2013-06-02T18:25:41.273Z
2013-06-02T18:25:41.273Z
Austin Buchanan
<p>I have no idea about your problem.  But I happen to know a great(est) <a href="http://web.eecs.umich.edu/~pettie/matching/">collection of papers pertaining to Graph Matching algorithms WITH PDFS</a>. Applause for Seth Pettie!</p>

CC BY-SA 3.0
2013-06-04T22:09:39.917Z
that's an awesome collection. Thanks for pointing it out !
Suresh Venkat
CC BY-SA 3.0
2013-06-10T15:13:32.970Z
This collection does not refer to the problem that I have described.
shuhalo
CC BY-SA 3.0
2013-06-04T08:04:39.570Z
2013-06-04T08:04:39.570Z
Yixin Cao
<p>The paper that @Austin Buchanan pointed to above on approximate Graph Isomorphism does not seem to correspond to the version asked. I am assuming that the adjacency matrix has $0,1$ entries in which case the objective is measuring only the matched edges. The approximate Graph Isomorphism model measures both the matched an unmatched edges which makes it a bit easier from an approximation point of view.</p>

<p>It appears that the problem asked is at least as hard the $k$-dense-subgraph problem which currently admits only a polynomial-approximation. See <a href="http://arxiv.org/abs/1001.2891" rel="nofollow">http://arxiv.org/abs/1001.2891</a> and <a href="http://arxiv.org/abs/1110.1360" rel="nofollow">http://arxiv.org/abs/1110.1360</a> for more details and the current status in terms of algorithms and hardness.</p>

<p>Now for the reduction. Suppose we want to solve the $k$-dense-subgraph problem in a graph $H$; that is we want to find a subset of $k$ nodes $S$ that maximizes the number of edges in the induced graph $G[S]$. You can reduce this to your problem by setting $G$ to be a graph consisting of a clique on $k$-vertices and $n-k$ isolated vertices, and $G'$ is set to be $H$. </p>

CC BY-SA 3.0
2013-06-05T19:19:08.217Z
2013-06-05T19:19:08.217Z
Chandra Chekuri
<p>Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from it when using search engines.</p>

<p>Given two graphs $G=(V,E)$ and $G'=(V',E')$ such that $|V| = |V'|$, the task is to find a bijection $\pi : V \rightarrow V'$ such that this bijection establishes as much correspondences between edges of $G$ and $G'$ as possible.</p>

<p>In other words, if $M$ and $M'$ are the adjascency matrices, then we want to maximize</p>

<p>$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$</p>

<p>This problem clearly contains graph isomorphism as a special case, and can be reduced to bipartite matching under a (non-polynomial!) reduction.</p>

<p>What kind of algorithms do exist, and what is known about its complexity?</p>

<reference-request><graph-theory><graph-isomorphism>
History and status of the graph matching problem
shuhalo
# History and status of the graph matching problem

(Asked by: username_0 on 2013-06-02)

Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from it when using search engines.

Given two graphs $G=(V,E)$ and $G'=(V',E')$ such that $|V| = |V'|$, the task is to find a bijection $\pi : V \rightarrow V'$ such that this bijection establishes as much correspondences between edges of $G$ and $G'$ as possible.

In other words, if $M$ and $M'$ are the adjascency matrices, then we want to maximize

$\sum\_{v,w \in V} M\_{v,w} \cdot M'\_{\pi(v),\pi(w)}$

This problem clearly contains graph isomorphism as a special case, and can be reduced to bipartite matching under a (non-polynomial!) reduction.

What kind of algorithms do exist, and what is known about its complexity?

**Tags:** reference-request, graph-theory, graph-isomorphism


---

## 3 answers

### Answer by username_1 on 2013-06-02. Score: 8

From the paper [Approximate Graph Isomorphism](http://link.springer.com/chapter/10.1007/978-3-642-32589-2_12):

> We study optimization versions of Graph Isomorphism. Given two graphs $G\_1,G\_2$, we are interested in finding a bijection $π$ from $V(G\_1)$ to $V(G\_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α < 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.


---

### Answer by username_2 on 2013-06-04. Score: 6

I have no idea about your problem. But I happen to know a great(est) [collection of papers pertaining to Graph Matching algorithms WITH PDFS](http://web.eecs.umich.edu/~pettie/matching/). Applause for Seth Pettie!

> **Comments:**
> **username_3**: that's an awesome collection. Thanks for pointing it out !  
> **username_0**: This collection does not refer to the problem that I have described.  

---

### Answer by username_4 on 2013-06-05. Score: 4

The paper that @username_1 pointed to above on approximate Graph Isomorphism does not seem to correspond to the version asked. I am assuming that the adjacency matrix has $0,1$ entries in which case the objective is measuring only the matched edges. The approximate Graph Isomorphism model measures both the matched an unmatched edges which makes it a bit easier from an approximation point of view.

It appears that the problem asked is at least as hard the $k$-dense-subgraph problem which currently admits only a polynomial-approximation. See <http://arxiv.org/abs/1001.2891> and <http://arxiv.org/abs/1110.1360> for more details and the current status in terms of algorithms and hardness.

Now for the reduction. Suppose we want to solve the $k$-dense-subgraph problem in a graph $H$; that is we want to find a subset of $k$ nodes $S$ that maximizes the number of edges in the induced graph $G[S]$. You can reduce this to your problem by setting $G$ to be a graph consisting of a clique on $k$-vertices and $n-k$ isolated vertices, and $G'$ is set to be $H$.


---

