An *exact graph matching problem* is a GMP (5), where the compatibility values of the matching objective are of the general form

$$\kappa_{i j}=\left\{\begin{array}{l l l}{{\alpha_{V}}}&{{:}}&{{{\mathbf{x}}_{i}={\mathbf{y}}_{j},\ i\in V(X),\ j\in V(Y)}}\\ {{\alpha_{E}}}&{{:}}&{{{\mathbf{x}}_{i}={\mathbf{y}}_{j},\ i\in E(X),\ j\in E(Y)}}\\ {{\alpha_{E}}}&{{:}}&{{i\in\overline{{{E}}}(X),\ j\in\overline{{{E}}}(Y)}}\\ {{0}}&{{:}}&{{\mathrm{otherwise}}}\end{array}\right.$$
$$\quad(6)$$

for all items i of X and j of Y . We require that the parameters αV , αE, and αE
are nonnegative such that αV +αE+αE > 0. Thus, exact matching problems only credit exact correspondences between items of X and Y . Standard formulations of the problems listed in Table 4.1 aim at maximizing the cardinality of vertices of the common substructure.

Thus, we may set αV = 1 and αE = αE = 0. If we want to maximize the cardinality of edges of the common substructure, we may set αE = 1 and αV = αE = 0. Other choices of the parameters αV , αE, and αE
reflect the importance of an exact association between corresponding items.

Different types of exact graph matching problems differ from the definition of the search space M as indicated in Table 4.1. Note that the special cases considered here are GMPs constrained over subsets of total morphisms. Clearly, subsets of total morphisms are not p-closed. Hence, in a strict sense, the special cases are not equivalent to clique search. To argue consistently, we regard a special case as an instance of the corresponding generic case, where we make an additional decision based on the optimal solution. For example, we think of the isomorphism problem as a MCISP, where we decide that both graphs under consideration are isomorphic if they have the same cardinality of vertices as a maximum clique in a derived association graph. Using this convention, we can show that the examples in Table 4.1 are equivalent to clique search in an association graph. Corollary 1. *Consider the GMP (5) with compatibility values of the form (6). Then* the problems listed in Table 4.1 are equivalent to the MWCP in an association graph.

Proof. From Proposition 1 follows that the sets of partial subgraph-, iso-, and homomorphisms are p-closed. For problems, which are maximized over total morphisms, we may relax M to partial morphisms without affecting the optimal solutions of (5), since αV , αE, and αE
are nonnegative with αV + αE + αE > 0. The assertion follows from Theorem 1.

## 4.2 Inexact Graph Matching Problems

In this subsection, we consider inexact graph matching problems. Again let X and Y be graphs with adjacency matrices X = (xij ) and Y = (yij ).

Best Common Subgraph Problems The *best common subgraph problem* is a GMP (5), where the compatibility values of the matching objective are arbitrary real values. The search space M is either the set of all partial morphisms or the set of all partial monomorphisms from X to Y .