It is well known that the MCISP is NP-complete [7]. Therefore, exact algorithms that guarantee to return an optimal solution are useless for all but the smallest graphs. In a practical setting, the time required to compute an optimal solution will typically reduce the overall *utility* of the algorthim. It is rather more desirable to trade quality with time and to provide near-optimal solutions within an acceptable time limit. Thus, it is conducive to consider local optimal solutions of (3). We say a partial isomorphism φ ∈ M is a local optimal solution if there is no other partial isomorphism from M with larger domain.

To solve the maximum common induced subgraph problem, we transform it to another combinatorial optimization problem using association graph techniques originally introduced by [1, 14, 2]. An association graph Z = X  Y of X and Y is a graph with vertex and edge set

$$\begin{array}{l}{{V(Z)=\left\{i r\,:\,x_{i i}=y_{r r}\right\}\subseteq V(X)\times V(Y)}}\\ {{E(Z)=\left\{(i r,j s)\,:\,x_{i j}=y_{r s}\right\}\subseteq V(Z)\times V(Z).}}\end{array}$$

The attributed adjacency matrix Z = (z*irjs*) of Z is defined by

$$z_{i r j s}=\left\{\begin{array}{l l l}{{1}}&{{:}}&{{i r=j s\mathrm{~and~}i r\in V(Z)}}\\ {{1}}&{{:}}&{{i r\neq j s\mathrm{~and~}(i j,r s)\in E(Z)}}\\ {{\epsilon}}&{{:}}&{{\mathrm{~otherwise}}}\end{array}\right.$$

for all *ir, js* ∈ V (Z). Thus, we assign to all vertices and edges of Z the weight 1 and to all non-edges the void attribute . Note that we derived the weights z*irjs* by inserting the corresponding compatibility values κ*ijrs*.

By definition of an association graph, we have the following useful equivalence relationship between between the partial isomorphisms from M and the cliques in Z:

- Z uniquely encodes each partial isomorphism φ from M as a clique Cφ in Z such that |D(φ)| = |C|.

- The set CZ(M) of cliques encoding partial isomorphisms is equal to the set CZ of all cliques in Z.
The above equivalence directly implies that the maximum (maximal) cliques of Z are in one-to-one correspondence with the global (local) optimal partial isomorphisms from M. Hence, solving the MCISP (3) is equivalent to solving the maximum clique problem in Z. Benefits of the Association Graph Framework What makes an association graph formulation of the MCISP so useful is that
- the maximum clique problem is mathematically well founded,

- it provides us access to a plethora of clique algorithms to solve the original problem,
- abstracts from the particularities of the graphs being matched, and