3.7.29. 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 a single state, see FigureΒ 5.23.3, while the πšŒπš‘πšŠπš—πšπšŽ and the πšœπš–πš˜πš˜πšπš‘ constraints have a counter-free non deterministic automaton, see FiguresΒ 5.61.5 andΒ 5.355.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 Berge-acyclic, where Berge-acyclic is defined by the following two conditions:

  1. There is no more than one shared variable between any pair of constraints,

  2. The hypergraph corresponding to the constraint network does not contain any cycle. WithinΒ [Berge87] a cycle of an hypergraph H is defined as β€œLet H be an hypergraph on a finite set X. A cycle of length k (kβ‰₯2) is a sequence (x 1 ,E 1 ,x 2 ,E 2 ,x 3 ,β‹―,E k ,x 1 ) such that (1)Β E 1 ,E 2 ,β‹―,E k are distinct edges of H, (2)Β x 1 ,x 2 ,β‹―,x k are distinct vertices of H, (3)Β x i ,x i+1 ∈E i (i=1,2,β‹―,k-1), (4)Β x k ,x 1 ∈E k .”

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.7. (A) and (D): Berge-acyclic constraint networks; (B) and (C): non Berge-acyclic constraint networks; (E), (F), (G), (H): corresponding intersection graphs.
ctrs/preface-147-tikz

PartsΒ (A), (B), (C) and (D) of FigureΒ 3.7.7 provide four examples of constraint networks, while partsΒ (E), (F), (G) andΒ (F) give their corresponding intersection graphs.

  1. The constraint network corresponding to partΒ (A) is Berge-acyclic since its corresponding intersection graphΒ (E) does not contain any cycle and since there is no more than one shared variable between any pair of constraints.

  2. The constraint network corresponding to partΒ (B) is not Berge-acyclic since its hypergraphΒ (B) contains a cycle.

  3. The constraint network corresponding toΒ (C) is also not Berge-acyclic since its third and fourth constraints share more than one variable.

  4. Finally, the constraint network corresponding toΒ (D) is Berge acyclic, even though its intersection graphΒ (H) has a cycle, since its hypergraphΒ (D) does not contain any cycle and since there is no more than one shared variable between any pair of constraints.

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 a 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.7 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.