Restriction and independence**. The** restriction of a function f : **Y → Z** to a set X ⊆ Y **is defined as**
f|X : X → Z, x 7→ f(x).

We define the restriction of a CSP P = (X, D, C**) to a set of variables** X
′ ⊆ X
by P|X ′ = (X
′, D|X ′ , C|X ′ **), where**
C|X ′ = {c ∈ C | vars(c) ⊆ X′}.

A non-empty proper subset **X ⊂ X** ˆ is independent in a CSP P = (X, D, C),
if and only if sol(P) = ∅ or sol(P)|Xˆ **= sol(**P|Xˆ).

For Xˆ independent in P, we say that P|Xˆ **is a** partial problem of P**. We can**
decompose P **if it has a partial problem.**
The key to an efficient implementation of Decompose **is to have an algorithmic interpretation of what it means that a CSP can be decomposed into partial**
problems. We now show that connected components in the constraint graph of a CSP represent independent partial problems.

A graph is connected **if and only if there exists a path between all nodes. A**
connected component of a constraint graph GP **is a maximal connected subgraph.** Proposition 1 Consider a CSP P = (X, D, C) with constraint graph GP . If X ⊂ X ˆ is a connected component in GP , then P|Xˆ is a partial problem of P.

Proof. There exists no hyperedge between node x ∈ Xˆ and node y /∈ X**ˆ, as**
connected components are maximal. This means that there is no constraint between any x and y in P. We have to distinguish two cases: If P **is unsatisfiable,**
Xˆ **is trivially independent (by definition of independence). Otherwise, take an**
arbitrary solution ˆs ∈ sol(P|Xˆ), and an arbitrary solution s ∈ sol(P). Merging ˆs into s **yields** s
′ = (x 7→ sˆ(x) for x ∈ Xˆ, x 7→ s(x**) otherwise). This** s
′
is again a solution of P, as all constraints on X \ Xˆ **are still satisfied, and all** constraints on Xˆ are satisfied, too. As we picked s and ˆs **arbitrarily, we get** sol(P)|Xˆ ⊇ sol(P|Xˆ). Because C|Xˆ of P|Xˆ covers all constraints of C **restricting**
Xˆ, it follows sol(P)|Xˆ ⊆ **sol(**P|Xˆ).

Therefore, it holds sol(P)|Xˆ **= sol(**P|Xˆ).

This result is not new [3, 10], but we repeat it to illustrate the central **algorithmic idea. Connected components can be computed in linear time in the size**
of the graph, and incremental algorithms are available. We can thus **implement**
Decompose **as a simple connectedness algorithm on the constraint graph that**
yields all partial problems of the current CSP.

Finding more than one non-empty connected component is a sufficient condition for finding partial problems, but not a necessary one. As an example, consider the CSP that contains the trivial constraint allowing all combinations