
| Tabelle 1: Examples of standard graph matching problems.   |                                                    |                                      |
|------------------------------------------------------------|----------------------------------------------------|--------------------------------------|
| Type                                                       | Graph Matching Problem                             | M ⊆ MXY                              |
| 1                                                          | Maximum Common Subgraph Problem                    | partial subgraph-morphisms           |
| →                                                          | Special case: Subgraph Isomorphism Problem         | total subgraph-morphisms             |
| 2                                                          | Maximum Common Induced Subgraph Problem            | partial isomorphisms                 |
| →                                                          | Special case: Induced Subgraph Isomorphism Problem | total isomorphisms to subgraph of Y  |
| →                                                          | Special case: Graph Isomorphism Problem            | total isomorphisms                   |
| 3                                                          | Maximum Common Homomorphic Subgraph Problem        | partial homomorphisms                |
| →                                                          | Special case: Subgraph Homomorphism Problem        | total homomorphisms to subgraph of Y |

From Φ ◦ Ψ = id on M and Ψ ◦ Φ = id on CZ, it follows that Φ is bijective. Finally, the assertion follows from

$$\omega(C)=\sum_{i r,j s\in C}z_{i r j s}=\sum_{i\in{\mathcal{D}}(\phi_{C})}\kappa_{i i\phi}=f(\phi_{C},X,Y).$$
$\square$

## 3.4 Implications Of Theorem 1

Theorem 1 has the following implications:
- Equivalence proofs now reduce to showing that the search space M of a GMP is p-closed for some property p.

- Theorem 1 is the starting point for generic continuous solutions to GMPs defined on p-closed search spaces. An equivalent continuous formulation of the MWCP is given in [10].

## 4 Application Of Theorem 1

The aim of this section is threefold: First, we show that common graph matching problems satisfy the necessary and sufficient condition. Second, we want to illustrate how the necessary and sufficient condition simplifies equivalence proofs. Third, we show the equivalence relationship for further examples, such as the graph edit distance, for which the desired relationship has been unproven.

## 4.1 Simple Exact Graph Matching Problems

In this subsection, we consider the problems listed in Table 4.1. For the first two types of problems equivalence to clique search is well-known. Homomorphic GMP of type 3 in Table 4.1 have been considered in a slight variation for attributed trees [3].