generalized association graph techniques by compiling results from [2,5,12] and showing that the maximum common (induced) subgraph problem and its derivations can be casted to a maximum clique problem. Pelillo [16] extended this collection by transforming the problem of matching free trees1to the MVCP so that connectivity is preserved.

Bunke [4] showed that for special cost functions, the error correcting graph matching problem and the maximum common subgraph are equivalent. As a consequence, special graph edit distances can be computed via clique search in an association graph. Schädler & Wysotzki [20] mapped the best monomorphic graph matching problem to a maximum weighted clique problem without presenting a sound theoretical justification of their transformation.

Although association graph techniques are attractive, an equivalence relationship between graph matching and clique search has been established only for certain classes of graph matching problems. Examples for graph matching problems, which have been proven equivalent to clique search in an association graph are the maximum common
(induced) subgraph and special cases thereof, or the graph and tree edit distance for special cost functions. To utilize the benefits of association graph techniques for a possibly broad range of graph matching problems, we pose the following question:
Under which conditions is graph matching equivalent to clique search in an association graph?

With the above question in mind, we make the following contributions:
- We formulate a necessary and sufficient condition (C), for graph matching problems to be equivalent to the maximum weight clique problem in an association graph. As opposed to standard formulations, the maximum weight clique problem takes into account weights assigned to both vertices and edges.

- Condition (C) is sufficiently strict to cover a broad range of graph matching problems. Besides the well-known standard problems, we show, for example, that determining the graph edit distance is equivalent to the maximum weight clique problem in an association graph.
- The mathematical framework developed in this paper provides a proof technique that reduces the problem of showing equivalence between graph matching and clique search to the problem of showing that a given graph matching problem satisfies condition (C). By means of a number of examples, we illustrate how the novel technique considerably simplifies equivalence proofs.

The paper is organized as follows. We conclude this section by introducing the terminology. Section 2 presents the background and an intuitive idea of condition (C). In Section 3, we formulate condition (C) and prove that (C) is necessary and sufficient for the desired equivalence realtionship. We apply (C) in Section 4. Finally, Section 5 concludes with a summary of the main results and an outlook on further research.

1A free tree is a directed acyclic graph without a *root*.

2