Arc Consistency

It has been proved that AC in the HVE is equivalent to GAC in the non-binary problem [Stergiou WalshStergiou Walsh1999]. Since the HVE is a binary CSP, one obvious way to apply AC is by using a generic AC algorithm. However, this results in redundant processing and an asymptotic time complexity worse than . To be precise, in the HVE of a problem with ary constraints we have binary constraints between dual and original variables. On such a constraint, AC can be enforced with worst-case time complexity. For the whole problem the complexity is .

Instead, we will now describe a simple AC algorithm that operates in the HVE and achieves the same worst-case time complexity as an optimal GAC algorithm applied in the non-binary representation. We can achieve this by slightly modifying the GAC algorithm of Bessiére and Régin br01 (GAC-2001). In Figure 3 we sketch the AC algorithm for the HVE, which we call HAC (Hidden AC).

Figure 3: HAC: an AC algorithm for the hidden variable encoding.
 16 1616 16 16 16 16 16 16 16 function 1: 2: for each dual variable 3: for each variable where 4: if 5: if is empty return INCONSISTENCY 6: put in each dual variable such that 7: return function 8: while is not empty 9: pop dual variable from 10: for each unassigned variable where 11: if 12: if is empty return INCONSISTENCY 13: put in each dual variable such that 14: return CONSISTENCY function 15: DELETION FALSE 16: for each value 17: if is not 18: if , and is 19: 20: else 21: remove from 22: for each such that 23: remove from each tuple such that 24: if is empty return INCONSISTENCY 25: DELETION TRUE 26: return DELETION

The HAC algorithm uses a stack (or queue) of dual variables to propagate value deletions, and works as follows. In an initialization phase it iterates over each dual variable (line 2). For every original variable constrained with the algorithm revises the constraint between and . This is done by calling function (line 4). During each revision, for each value of we look for a tuple in the domain of that supports it. As in AC-2001, we store : the most recent tuple we have found in that supports value of variable 2. If this tuple has not been deleted from then we know that is supported. Otherwise, we look for a new supporting tuple starting from the tuple immediately after . If no such tuple is found then is removed from (line 21). In that case, all tuples that include that value are removed from the domains of the dual variables that are constrained with (lines 22-23). If these dual variables are not already in the stack they are added to it3. Then, dual variables are removed from the stack sequentially. For each dual variable that is removed from the stack, the algorithm revises the constraint between and each original variable constrained with . The algorithm terminates if all the values in a domain are deleted, in which case the problem is not arc consistent, or if the stack becomes empty, in which case the problem is arc consistent.

The main difference between HAC and GAC-2001 is that GAC-2001 does not include lines 22-24. That is, even if the non-binary constraints are given in extension, GAC-2001 does not remove tuples that become invalid from the lists of allowed tuples. As a result, the two algorithms check for the validity of a tuple (in lines 17 and 18) in different ways. Later on in this section we will explain this in detail. Apart from this difference, which is important because it affects their run times, the two algorithms are essentially the same. We can move from HAC to GAC-2001 by removing lines 22-24 and substituting any references to dual variables by references to the corresponding constraints. For example, corresponds to in GAC-2001, i.e. the last tuple in constraint that supports value of variable . Note that in such an implementation of GAC-2001, propagation is constraint-based. That is, the algorithm utilizes a stack of constraints to perform the propagation of value deletions.

Subsections
Nikolaos Samaras 2005-11-09