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
ctrs/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 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 CTR 1 , CTR 4 , CTR 2 , CTR 3 , CTR 2 , CTR 4 , CTR 1 .

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