### 3.7.27. Berge-acyclic constraint network

A constraint for which the decomposition associated with its usually counter -free deterministic automatonAll the above constraints, except $\mathrm{𝚊𝚖𝚘𝚗𝚐}$, $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$, and $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ have a deterministic counter -free automaton. The $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraint has an automaton involving one counter and one single state, see Figure 5.16.2, while the $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ and the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraints have a counter -free non deterministic automaton, see Figures 5.49.4 and 5.298.4. is Berge -acyclic. Arc -consistency for a Berge -acyclic constraint network is achieved by making each constraint of the corresponding network arc -consistent [BeeriFaginMaierYannakakis83]. A constraint network for which the corresponding intersection graph does not contain any cycle and such that, for any pair of constraints, the two sets of involved variables share at most one variable is so -called Berge -acyclic. The intersection graph of a constraint network is built in the following way: to each vertex corresponds a constraint and there is an edge between two vertices if and only if the sets of variables involved in the two corresponding constraints intersect.

Parts (A), (B) and (C) of Figure 3.7.6 provide three examples of constraint networks, while parts (D), (E) and (F) give their corresponding intersection graph. The constraint network corresponding to part (A) is Berge -acyclic, while the constraint network associated with (B) is not (since its corresponding intersection graph (E) contains a cycle). Finally the constraint network depicted by (C) is also not Berge -acyclic since its third and fourth constraints share more than one variable.

If we execute the filtering algorithm of each constraint of a Berge -acyclic constraint network $𝒩$ in an appropriate order then each constraint needs only to be waken twice in order to reach the fix -point. A static ordering for waking the constraints of $𝒩$ can be determined as follows:

• Consider the intersection graph ${𝒢}_{𝒩}$ associated with the constraint network $𝒩$. We perform a topological sort on ${𝒢}_{𝒩}$, which always first selects in the remaining part of ${𝒢}_{𝒩}$ a vertex (i.e., a constraint) which has only one single neighbour. Let ${C}_{1},{C}_{2},...,{C}_{n}$ be the constraints successively removed by the topological sort.

• Then, the static ordering for reaching a fix -point is given by the sequence ${C}_{1},{C}_{2},...,{C}_{n-1},{C}_{n},{C}_{n-1},...,{C}_{2},{C}_{1}$, where each constraint is woken at most twice. This can be done by using the notion of propagator group [LagerkvistSchulte09]. This facility allows the user of a solver controlling the order of execution of a group of constraints. Propagator groups are useful, both to guaranty the theoretical worst case complexity of a decomposition, and for accelerating convergence to the fix -point in practice.

If we consider the Berge -acyclic constraint network given by Part (D) of Figure 3.7.6 an appropriate order for waking the constraints could for instance be ${\mathrm{CTR}}_{1}$, ${\mathrm{CTR}}_{4}$, ${\mathrm{CTR}}_{2}$, ${\mathrm{CTR}}_{3}$, ${\mathrm{CTR}}_{2}$, ${\mathrm{CTR}}_{4}$, ${\mathrm{CTR}}_{1}$.

For heuristics that try creating a Berge -acyclic constraint network see also the keyword heuristics and Berge-acyclic constraint network.