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 , , and have a deterministic counter -free automaton. The constraint has an automaton involving one counter and one single state, see Figure 5.16.2, while the and the 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.
Figure 3.7.6. Illustration of Berge -acyclic constraint network
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 be the constraints successively removed by the topological sort.
Then, the static ordering for reaching a fix -point is given by the sequence , 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 , , , , , , .
For heuristics that try creating a Berge -acyclic constraint network see also the keyword heuristics and Berge-acyclic constraint network.