to the subsets of S by considering their local behavior. A subset S
0 ⊆ S satisfies property p if p(x) = 1 for each element x ∈ S0, i.e. if S
0locally satisfies p.

Next, we characterize an association graph Z = X Y by means of a property. To this end, we consider the complete graph ZXY defined on the vertex set VXY = V (X)×V (Y ).

Let p be a property on the set IXY = I(ZXY ) of items such that the vertices and edges of Z are all the items that satisfy p. Hence, the subsets of IXY that satisfy property p are the induced subgraphs of Z induced by its cliques. We can express the set of all cliques in Z as CZ = {U ⊆ IXY : U satisfies p}. Now using p, we rewrite condition CZ(M) = CZ as follows: There is a property p *such that* CZ(M) = {C ∈ CZ : C *satisfies* p}. Since the cliques from CZ(M) encode the feasible morphisms from M, we may directly translate the last condition to a condition on the search space M:
(C) There is a property p **such that** M = {φ ∈ MXY : φ *satisfies* p}.

To summarize, we claim that condition (C) is necessary and sufficient for the equivalence relationship in question.

## 3 A Necessary And Sufficient Condition

The aim of this section is to prove that condition (C) is necessary and sufficient for equivalence between graph matching and clique search in an association graph.

## 3.1 Closed Sets Of P**-Morphisms**

Here, we consider properties p defined on the set IXY = I(X) × I(Y ) of pairs of items from X and Y . Let (i, r) ∈ IXY . We say, items i and r are p*-similar*, written as i ∼p r, if (i, r) satisfies property p. Let us consider some examples.

Example 2. Let (i, r) ∈ IXY , and let all morphisms φ **be partial morphisms from** MXY .

Then the following examples are properties on IXY :
1. i ∼p r = there is a partial (mono-, subgraph-, homo-, iso-) morphism φ *with* i φ = j.

2. i ∼p r = there is a partial connectivity preserving isomorphism φ *with* i φ = j.

Next, we apply the notion of property on IXY = I(X) × I(Y ) to partial morphisms.

To this end, we identify a partial morphism φ ∈ MXY with the binary relation Γ(φ) = (i, r) ∈ D(φ) × R(φ) : i φ = r	⊆ IXY .

We say, φ is a p*-morphism* if Γ(φ) is a subset of the set R
p XY =(i, r) ∈ IXY : i ∼p r	.

In informal terms, a partial morphism φ satisfies property p if it locally satisfies p. To illustrate the defintion of p-morphism, we provide some examples. Example 3. Consider the properties p *of Example 2.*