As explained, the main difference between the AC algorithm for the HVE and the corresponding GAC algorithm is the fact that the AC algorithm has to update the domains of the dual variables as well as the original ones. This incurs a time overhead, but as we will show, deleting values from dual variables can help propagation discover domain wipe-outs in arc inconsistent problems faster.
Proof: First, consider that if no domain wipeout in any variable (original or dual) occurs then the two algorithms will add constraints (dual variables) to the stack and remove them for revision in exactly the same order. Therefore, we only need to show that if a value is deleted from a variable during the revision of a constraint or finds a new support in the constraint then these operations will require the same number of checks in both representations. Assume that in the non-binary version of the algorithm value is deleted from the domain of variable because it has no support in constraint . If is the number of allowed tuples in then determining the lack of support will require checks, one for each of the tuples in that have not been checked yet. If the value is not deleted but finds a new support , with , then checks will be performed. In the HVE, will be processed in the same order as in the non-binary version and we will require or checks depending on the case. Obviously, is the same as since a tuple in corresponds to a value in , and therefore, the same number of checks will be performed in both representations.
Proof: In any CSP, arc inconsistency in detected when the domain of a variable is wiped out while applying AC. In the HVE of a non-binary CSP, arc inconsistency is detected when the domain of an original variable is wiped out or (crucially) when the domain of a dual variable is wiped out. The second possibility can make an AC algorithm that operates in the HVE more efficient than the corresponding GAC algorithm. To prove this consider an arc inconsistent non-binary problem. Assume that the domain of original variable is wiped out during the processing of constraint which is encoded as a dual variable in the HVE. Until the point where function is called with and as arguments, there is no inconsistency and according to Proposition 8.1 the GAC algorithm and the AC algorithm on the HVE will perform the same number of consistency checks. Assume that there are values left in before the call to . In function we will unsuccessfully look for a support for each of the values. If is the number of allowed tuples in then, for each value , this will require checks for the GAC algorithm and checks for the AC algorithm. Since = , the two algorithms will perform the same number of consistency checks to detect the domain wipeout.
The following example demonstrates that HAC may discover the inconsistency with less checks. Consider a problem with variables , , , which have domains , , , and , respectively. There are two constraints, and , with and respectively. Value 0 of is supported in by tuples that include the assignment . Value 0 of is supported in by tuples that include the assignment . Constraint allows only tuples that include the assignment . Values of are supported in by tuples that include and by tuples that include . Now assume that variable is instantiated to 0, which means that the deletion of 1 from must be propagated. In the HVE, we will first delete all tuples that include the value from dual variables and . Then, we will add dual variables and to the stack, remove them, and revise all original variables connected to them. Assuming that is removed first, value 0 of will have no support in so it will be deleted. As a result, we will delete all tuples from dual variable that include the pair . This means that the domain of will be wiped out. In the non-binary representation, we will proceed in a similar way and perform the same number of checks until 0 is deleted from . After that deletion the algorithm will look for supports in for value 1 of and all values of . This will involve checks that are avoided in the HVE. The inconsistency will be discovered later when we process constraint and find out that value 1 of has no support in resulting in the domain wipeout of .
Nikolaos Samaras 2005-11-09