- abstracts from the constraints on feasible matches.

The benefits of the second item on clique algorithms is worth to be discussed in more detail. Both the MCISP and the maximum clique problem are combinatorial problems. Solution techniques for combinatorial problems can be classified into two groups:

- *Discrete methods* generate a sequence of suboptimal or partial solutions to the original problem. This process is guided by local search combined with techniques to escape from local optimal solutions.

- *Continuous methods* embed the discrete solution space in a larger continuous one.

Exploiting the topological and geometric properties of the continuous space, the algorithm creates a sequence of points that converges to the solution of the original problem.
Discrete approaches suffer from problems having a large number of local maxima. On the other hand, continuous approaches such as interior point methods reveal to be efficient solutions to large scale combinatorial optimization problems. Hence, using association graph techniques provides us access to those efficient continuous solutions. Shortcomings of the Association Graph Framework Despite its long tradition and benefits, the association graph formulation still suffers from the following shortcomings:
- It is unclear which graph matching problems are equivalent to clique search in an association graph. The equivalence relationship in question has been proved only for selected problems. For example, Chen & Yun [6] compiled results from
[2, 5, 12], showing that the maximum common (induced) subgraph problem and its derivations can be casted to a maximum clique problem. Pelillo and his co-workers extended this collection for different types of tree matching problems [3, 18, 17, 16].

- In all these examples, equivalence proofs of graph matching and clique search follow the same recurring pattern: First construct an appropriate association graph and then establish a bijective mapping between cliques and morphisms. There is no mathematical framework that reduces equivalence proofs to showing that the preconditions of some generic equivalence relationship between graph matching and clique search are satisfied.

## What We Want

The aim is to remove both shortcomings addressed in the previous paragraph. We want to formulate a necessary and sufficient condition (C) for equivalence between graph matching and clique search. The existence of condition (C) explains which graph matching problems are equivalent to clique search in an association graph and reduces equivalence proofs to showing that a given graph matching problem satisfies (C). In addition, we want to indicate by a number of examples that a broad range of graph matching problems satisfy condition (C) and are therefore equivalent to clique search in an association graph.