of values for x and y. Then x and y **may still be independent, but the constraint**
graph shows a hyperedge connecting the two variables, so that x and y **will always end up in the same connected component. In the following section, we will**
see how propagation-based solvers can deal with this.

## 4 How Dds Interacts With Propagation And Search

The previous section showed how DDS can be integrated into a propagationbased solver. But what are the consequences, how is decomposition affected by propagation and search, and how can it benefit from the search heuristic?

## 4.1 Constraint Graph Dynamics

Decomposition examines the constraint graph during search**. This is vital as** propagation and search modify **the constraint graph dynamically - they narrow** the domains of the problem's variables and remove some entailed constraints. The result is a sparser constraint graph with more potential for decomposition: Assignment. Clearly, an assigned variable (|D(x)| **= 1) is independent of all**
other variables of the CSP. This implies that connections of hyperedges to assigned variables can be removed from the constraint graph - the constraint graph becomes sparser. Assignment increases the potential for **decomposition,** since an assigned variable may have been responsible for keeping two **otherwise** independent parts of the graph connected. Entailment. Consider the example CSP P = (X, D, C**) from the end of the** previous section, where variables x ∈ X and y ∈ X **are connected by a trivial** constraint c ∈ C allowing all possible value tuples. Obviously, c **is entailed in** P, it will not contribute to propagation any more. Formally, we have for P
′ =
(X, D, C \ {c}**) that sol(**P
′) = sol(P**). It is also obvious that the constraint graph**
for P
′is sparser than the one for P**, it contains one edge less. It is thus vital**
to our approach to detect entailment of constraints as early as possible, and to remove entailed constraints from C. Clearly, full entailment detection is coNPcomplete. Most CP systems (e.g. Gecode) however implement a weak **form of**
entailment detection in order to remove propagators early, which our approach automatically benefits from.

## 4.2 Search Heuristics

The applied search heuristic, encoded by LeftChoice and RightChoice, is extremely important for the efficiency of the search. In particular, dynamic heuristics, natively supported by DDS, are known to be largely superior to **static ones.**
In the following (and for our implementation) we refer to the common variablevalue heuristics that select a variable x and a value v ∈ D(x**). Afterwards, the disjunction is done by** LeftChoice(P) = (X, D, C∪(x⋄v**)) and** RightChoice(P) =
(X, D, C ∪ ¬(x ⋄ v)), where ⋄ **is some binary relation.**
7