We know that AC in the DE is strictly stronger than GAC in the non-binary representation and AC in the HVE [Stergiou WalshStergiou Walsh1999]. Since the DE is a binary CSP, one obvious way to apply AC is using a generic AC algorithm. The domain size of a dual variable corresponding to a ary constraint is in the worst case. Therefore, if we apply an optimal AC algorithm then we can enforce AC on one dual constraint with worst-case complexity. In the DE of a CSP with constraints of maximum arity there are at most binary constraints (when all pairs of dual variables share one or more original variables). Therefore, we can enforce AC in the DE of the CSP with worst-case complexity. This is significantly more expensive compared to the complexity bound of GAC in the non-binary representation and AC in the HVE. Because of the very high complexity bound, AC processing in the DE is considered to be impractical, except perhaps for very tight constraints.
However, we will now show that AC can be applied in the DE much more efficiently. To be precise we can enforce AC on the DE of a non-binary CSP with worst-case time complexity. The improvement in the asymptotic complexity can be achieved by exploiting the structure of the DE; namely, the fact that the constraints in the DE are piecewise functional.
Consider a binary constraint between dual variables and . We can create a piecewise decomposition of the tuples in the domain of either dual variable into groups such that all tuples in a group are supported by the same group of tuples in the other variable. If the non-binary constraints corresponding to the two dual variables share original variables of domain size , then we can partition the tuples of and into groups. Each tuple in a group includes the same sub-tuple of the form , where . Each tuple in will be supported by all tuples in a group of the other variable, where each tuple in also includes the sub-tuple .The tuples belonging to will be the only supports of tuple since any other tuple does not contain the sub-tuple . In other words, a group of tuples in variable will only be supported by a corresponding group in variable where the tuples in both groups have the same values for the original variables that are common to the two encoded non-binary constraints. Therefore, the constraints in the DE are piecewise functional.
Van Hentenryck, Deville & Teng vhdt92 have shown that AC can be achieved in a set of binary piecewise functional constraints with worst-case time complexity, an improvement of compared to the complexity of arbitrary binary constraints [Van Hentenryck, Deville, TengVan Hentenryck et al.1992]. Since we showed that the constraints in the DE are piecewise functional, the result of Van Hentenryck et al. vhdt92 means that we can improve on the complexity of AC in the DE.
In Figure 4 we sketch an AC-3 like AC algorithm specifically designed for the DE, which we call PW-AC ( PieceWise Arc Consistency). As we will show, this algorithm has a worst-case time complexity of . The same complexity bound can be achieved by the AC-5 algorithm of Van Hentenryck et al. vhdt92, in its specialization to piecewise functional constraints, with the necessary adaptations to operate in the DE. As do most AC algorithms, PW-AC uses a stack (or queue) to propagate deletions from the domains of variables. This stack processes groups of piecewise decompositions, instead of variables or constraints as is usual in AC algorithms. We use the following notation:
The algorithm works as follows. In an initialization phase, for each group we count the number of tuples it contains (lines 3-6). Then, for each variable we iterate over the variables that are constrained with . For each group of , we check if is empty or not (line 10). If it is empty, it is added to the stack for propagation.
In the next phase, function is called to delete unsupported tuples and propagate the deletions (line 12). Once the previous phase has finished, the stack will contain a number of groups with 0 cardinality. For each such group we must remove all tuples belonging to group since they have lost their support. This is done by successively removing a group from the stack and calling function . Since group has lost its support, each tuple that belongs to is deleted (lines 20-21). Apart from , tuple may also belong to other groups that is partitioned in with respect to constraints between and other variables. Since is deleted, the counters of these groups must be updated (i.e. reduced by one). This is done in lines 22-23. In the implementation we use function to access the relevant groups. If the counter of such a group becomes 0 then the group is added to the stack for propagation (lines 24-25 and 18). The process stops when either the stack or the domain of a variable becomes empty. In the former case, the DE is AC, while in the latter it is not.
The following example illustrates the advantage of algorithm PW-AC over both a generic AC algorithm employed in the DE, and AC in the HVE (or GAC in the non-binary representation).
Now consider the HVE of the problem. Applying AC on the HVE will have no effect because values 0 and 1 of and are both supported in and . Therefore there is no propagation through these variables, and as a result the two tuples of will not be deleted. Similarly, there will be no propagation if we apply GAC in the non-binary representation of the problem.
Note that the theoretical results regarding the DE presented in the rest of the paper hold if the AC-5 algorithm of Van Hentenryck et al. vhdt92 was adapted and used the DE instead of PW-AC. The two algorithms have some similarities (e.g. they both use a function to access the group of a decomposition that a certain tuple belongs to, though implemented differently), but their basic operation is different. The algorithm of Van Hentenryck et al. vhdt92, being an instantiation of AC-5, handles a queue of triples to implement constraint propagation, where and are two variables involved in a constraint and is a value that has been removed from . PW-AC utilizes a queue of piecewise decompositions. Also the data structures used by the algorithms are different. PW-AC checks and updates counters to perform the propagation which, as we explain below, requires space exponential in the number of common variables in the non-binary constraints. The algorithm of Van Hentenryck et al. vhdt92 utilizes a more complicated data structure which requires space exponential in the arity of the non-binary constraints. It has to be noted, however, that PW-AC is specifically designed for the DE. That is, its operation, data structures, and the way it checks for consistency are based on the fact that the domains of the dual variables consist of the tuples of the original constraints extensionally stored. On the other hand, the algorithm of Van Hentenryck et al. vhdt92 is generic, in the sense that it can be adapted to operate on any piecewise functional constraint.