History and status of the graph matching problem

Question

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?

Answer 1

From the paper Approximate Graph Isomorphism:

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 2

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. Applause for Seth Pettie!

Answer 3

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.

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