Appendix A

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.

Proposition 8.1   Let $P$ be a non-binary CSP. Assume that after generalized arc consistency is applied in $P$, there is no domain wipeout in the resulting problem. Enforcing arc consistency in the hidden variable encoding of $P$ using HAC requires the same number of consistency checks as enforcing generalized arc consistency in $P$ using GAC-2001, assuming the two algorithms follow the same ordering of variables and values when looking for supports and propagating deletions.

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 $a$ is deleted from the domain of variable $x_i$ because it has no support in constraint $c$. If $\vert T\vert$ is the number of allowed tuples in $c$ then determining the lack of support will require $\vert T\vert-currentSupport_{x_i,a,c}$ checks, one for each of the tuples in $c$ that have not been checked yet. If the value is not deleted but finds a new support $\tau$, with $\tau>currentSupport_{x_i,a,c}$, then $\tau-currentSupport_{x_i,a,c}$ checks will be performed. In the HVE, $x_i$ will be processed in the same order as in the non-binary version and we will require $\vert T\vert-currentSupport_{x_i,a,v_c}$ or $\tau-currentSupport_{x_i,a,v_c}$ checks depending on the case. Obviously, $currentSupport_{x_i,a,c}$ is the same as $currentSupport_{x_i,a,v_c}$ since a tuple in $c$ corresponds to a value in $v_c$, and therefore, the same number of checks will be performed in both representations. $\Box$

Proposition 8.2   Let $P$ be a non-binary CSP. Assume that the application of generalized arc consistency in $P$ results in a domain wipeout. Algorithm HAC applied in the hidden variable encoding of $P$ discovers the domain wipeout with at most the same number of consistency checks as algorithm GAC-2001 in the non-binary representation, assuming the two algorithms follow the same ordering of variables and values when looking for supports and propagating deletions.

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 $x_i$ is wiped out during the processing of constraint $c$ which is encoded as a dual variable $v_c$ in the HVE. Until the point where function $Revise$ is called with $x_i$ and $c$ 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 $j$ values left in $D(x_i)$ before the call to $Revise$. In function $Revise$ we will unsuccessfully look for a support for each of the $j$ values. If $\vert T\vert$ is the number of allowed tuples in $c$ then, for each value $a\in D(x_i)$, this will require $\vert T\vert-currentSupport_{x_i,a,c}$ checks for the GAC algorithm and $\vert T\vert-currentSupport_{x_i,a,v_c}$ checks for the AC algorithm. Since $\vert T\vert-currentSupport_{x_i,a,c}$ = $\vert T\vert-currentSupport_{x_i,a,v_c}$, 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 $x_1$, $x_2$, $x_3$, $x_4$ which have domains $\{0,1\}$, $\{0,1\}$, $\{0,\ldots,9\}$, and $\{0,1\}$, respectively. There are two constraints, $c_1$ and $c_2$, with $vars(c_1)=\{x_1,x_2,x_3\}$ and $vars(c_2)=\{x_1,x_2,x_4\}$ respectively. Value 0 of $x_2$ is supported in $c_1$ by tuples that include the assignment $(x_1,1)$. Value 0 of $x_1$ is supported in $c_2$ by tuples that include the assignment $(x_2,0)$. Constraint $c_2$ allows only tuples that include the assignment $(x_2,0)$. Values $0,\ldots,9$ of $x_3$ are supported in $c_1$ by tuples that include $(x_2,0)$ and by tuples that include $(x_2,1)$. Now assume that variable $x_1$ is instantiated to 0, which means that the deletion of 1 from $D(x_1)$ must be propagated. In the HVE, we will first delete all tuples that include the value $(x_1,1)$ from dual variables $v_{c_1}$ and $v_{c_2}$. Then, we will add dual variables $v_{c_1}$ and $v_{c_2}$ to the stack, remove them, and revise all original variables connected to them. Assuming that $v_{c_1}$ is removed first, value 0 of $x_2$ will have no support in $v_{c_1}$ so it will be deleted. As a result, we will delete all tuples from dual variable $v_{c_2}$ that include the pair $(x_2,0)$. This means that the domain of $v_{c_2}$ 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 $x_2$. After that deletion the algorithm will look for supports in $c_1$ for value 1 of $x_2$ and all values of $x_3$. This will involve checks that are avoided in the HVE. The inconsistency will be discovered later when we process constraint $c_2$ and find out that value 1 of $x_2$ has no support in $c_2$ resulting in the domain wipeout of $x_2$. $\Box$