Corollary 4. Let X and Y *be attributed graphs. Then the graph edit distance problem* is equivalent to the MWCP in Z = X0  Y
0, where X0 and Y
0 **are the dummy extensions**
of X and Y .

Proof. Proposition 1 and Theorem 1.

Solving the graph edit distance by clique search in Z = X0  Y
0is impractical, because the dummy extensions double the total number of vertices of both original graphs. In a practical implementation, it is sufficient to expand each of both graphs X and Y by adding only one dummy vertex as described above. This leads to a formulation of the graph matching problem constrained over relations φ ⊆ V (X)×V (Y ) rather than partial morphisms. Though the theory developed in this contribution also holds for relations, we do not consider the more general case for the sake of clarity.

## 5 Conclusion

We presented a necessary and sufficient condition (C) for graph matching to be equivalent to the maximum weight clique problem in an association graph. The implications of this result are as follows: first, equivalence proofs now reduce to showing that condition
(C) holds; second, the condition (C) is applicable to a broad range of common graph matching problems; third, generic continuous solutions can now be applied to all graph matching problems that satisfy (C).

We showed that the graph edit distance problem, probabilistic graph matching, the best common graph matching, and the maximum common homomorphic subgraph problem are equivalent to clique search in a derived association graph.

One limitation with this framework motivates further research: The maximum weight clique problem, where weights are assigned to both vertices and edges has been rarely studied in the literature. Hence, it is conducive to develop special continuous formulations and solutions to the maximum weight clique problem in order to obtain a generic graph matching solver.

## Literatur

[1] A.P. Ambler, H.G. Barrow, C.M. Brown, R.M. Burstall, and R. J. Popplestone. A
versatile computer-controlled assembly system. In *International Joint Conference* on Artificial Intelligence, pages 298–307. Stanford University, California, 1973.

[2] H. Barrow and R. Burstall. Subgraph isomorphism, matching relational structures and maximal cliques. *Information Processing Letters*, 4:83–84, 1976.

[3] M. Bartoli, M. Pelillo, K. Siddiqi, and S.W. Zucker. Attributed tree homomorphism using association graphs. In **Proceedings of the IEEE International Conference on**
Pattern Recognition, pages 2133–2136, 2000.