The *maximum weight clique problem* is a combinatorial optimization problem of the
form
$$\begin{array}{ll}\mbox{maximize}&\omega(C)=\sum_{i,j\in C}x_{ij}\\ \mbox{subject to}&C\in{\cal C}_{X},\end{array}$$
$$\left(2\right)$$
where CX is the set of all cliques of X.

A *maximal weight clique* of X is a clique C ∈ CX such that

$$C\subseteq C^{\prime}\;\Rightarrow\;\omega(C)\geq\omega(C^{\prime})$$

for all cliques C
0 of X. It is impossible to enlarge a maximal weight clique C to a clique with higher weight. If all vertices and edges of X are associated with positive weights, a maximal weight clique is not a proper subset of another clique. A *maximum weight* clique of X is a clique C ∈ CX with maximum total weight over its vertices and edges.

By C
×
X we denote the set of all maximal cliques and by C
∗
X the set of all maximum cliques of X.

## 2 Background

The aim of this section is twofold: First, it introduces the problem and motivates its solution. To this end, we consider the classical maximum common induced subgraph problem (MCISP). Second, it provides an intuitive idea of how to solve that problem in a more general setting.

## 2.1 The Problem

To set the scene, we consider the MCISP. Given two graphs X and Y , the *MCISP* asks for a partial isomorphism φ : V (X) → V (Y ) that maximizes the cardinality |D(φ)| of its domain. This optimization problem is called MCISP, because each partial isomorphism φ between X and Y is an isomorphism between the induced subgraphs X[D(φ)] and Y [R(φ)]. Since maximizing |D(φ)| 2instead of |D(φ)| does not effect the problem, we may rewrite the MCISP as

$$\begin{array}{l l}{{\mathrm{maximize}}}&{{\quad f\left(\phi,X,Y\right)=|\mathcal{D}(\phi)|^{2}=\sum_{i,j\in\mathcal{D}(\phi)}\kappa_{i j}{}^{\phi}j^{\phi}}}\\ {{\mathrm{subject~to}}}&{{\quad\phi\in\mathcal{M},}}\end{array}$$
$$\left({\boldsymbol{4}}\right)$$
$$\quad(3)$$

where the *search space* M is the set of all partial isomorphisms from X to Y . The values κijrs ∈ {0, 1} are the *compatibility values* with

$$\kappa_{i j r s}=\left\{\begin{array}{l l l}{{1}}&{{:}}&{{x_{i j}=y_{r s}}}\\ {{0}}&{{:}}&{{\mathrm{otherwise}}}\end{array}\right.$$

for all *i, j* ∈ V (X) and *r, s* ∈ V (Y ). A compatibility value κ*ijrs* indicates whether item
(*i, j*) of X has the same attribute as item (*r, s*) of Y . The *matching objective* f counts the number of items from X consistently mapped to their exact counterparts in Y .