
## 1.1 Preliminaries

The aim of this subsection is to introduce the terminology and notations used througout this contribution. We assume knowledge about basic graph theory.

## Basic Graph Theory

Graphs For convenience of presentation, all graphs are undirected without loops. The graphs we consider are triples X = (*V, E,* X) consisting of a finite set V = V (X) of vertices, a set E = E(X) of edges, and an *attributed adjacency matrix* X = (xij ) with elements xij from a set of **attributes** *A ∪ {*}. Elements xij ∈ A are attributes either assigned to vertices if i = j or to edges if (*i, j*) ∈ E. We label non-edges (*i, j*) ∈E with a distinguished *void attribute* xij = .

Subgraphs We write X0 ⊆ X to denote that X0is a subgraph of X. For a subset U of V (X), the graph X[U] denotes the induced subgraph of X induced by U. Items To unclutter the text from tedious case distinctions, we occasionally make use of the notion of *item*. Items of X are elements from I(X) = V ×V . Thus, an item i = (*i, j*)
of X is either a vertex if i = j, an edge if i ∈ E(X), or a non-edge if i ∈E(X).

Morphisms Let X and Y be graphs. A *morphism* from X to Y is a mapping

$$\phi:V(X)\to V(Y),\quad i\mapsto i^{\phi}.$$

A *partial morphism* from X to Y is a morphism φ defined on a subset of V (X). By D(φ) we denote the *domain* and by R(φ) the *range* of a partial morphism φ. By abuse of notation we occasionally write i = (i, j) ∈ D(φ) if i ∈ D(φ) and j ∈ D(φ). The meaning of i ∈ R(φ) is now obvious. A *monomorphism* is an injective morphism. We use the notions *homo-* and *isomorphism* as in standard graph theory. A partial *subgraphmorphism* is an isomorphism between subgraphs.

## The Maximum Weight Clique Problem

Let X = (*V, E,* X) be a graph with attributes from A = R ∪ {}. A *clique* of X is a subset C ⊆ V such that the induced subgraph X[C] is complete. A clique is said to be *maximal* if C is not contained in any larger clique of X, and *maximum* if C has maximum cardinality of vertices. The *weight* ω(C) of a clique C of X is defined by

$$\omega(C)=\sum_{i,j\in C}x_{i j}.$$
xij . (1)
The weight of a clique C is the total of all vertex and edge weights of the subgraph X[C]
induced by C. Since the vertices of X[C] are mutually adjacent, the void symbol  does not occur in the sum of (1). Hence, ω(C) is well-defined.

$$(1)$$
