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