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 $O(ekd^{k})$. To be precise, in the HVE of a problem with $k-$ary constraints we have $ek$ binary constraints between dual and original variables. On such a constraint, AC can be enforced with $O(dd^k)$ worst-case time complexity. For the whole problem the complexity is $O(ekd^{k+1})$.

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 $HAC$


1:		$Q\leftarrow \emptyset$


2:		for each dual variable $v_j$


3:				for each variable $x_i$ where $x_i\in vars(c_{v_j})$


4:						if $Revise(x_i,v_j)=TRUE$


5:								if $D(x_i)$ is empty return INCONSISTENCY


6:								put in $Q$ each dual variable $v_l$ such that $x_i\in vars(c_{v_l})$


7:		return $Propagation$




function $Propagation$


8:		while $Q$ is not empty


9:				pop dual variable $v_j$ from $Q$


10:				for each unassigned variable $x_i$ where $x_i\in vars(c_{v_j})$


11:						if $Revise(x_i,v_j)=TRUE$


12:								if $D(x_i)$ is empty return INCONSISTENCY


13:								put in $Q$ each dual variable $v_l$ such that $x_i\in vars(c_{v_l})$


14:		return CONSISTENCY




function $Revise(x_i,v_j)$


15:		DELETION $\leftarrow$ FALSE


16:				for each value $a\in D(x_i)$


17:						if $currentSupport_{x_i,a,v_j}$ is not $valid$


18:								if $\exists\ \tau (\in\ D(v_j))>_{lex}\
currentSupport_{x_i,a,v_j}$, $\tau[x_i]=a$ and $\tau$ is $valid$


19:										$currentSupport_{x_i,a,v_j}\leftarrow \tau$


20:								else


21:										remove $a$ from $D(x_i)$


22:										for each $v_l$ such that $x_i\in vars(c_{v_l})$


23:												remove from $D(v_l)$ each tuple $\tau'$ such that $\tau'[x_i]=a$


24:												if $D(v_l)$ is empty return INCONSISTENCY


25:										DELETION $\leftarrow$ 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 $v_j$ (line 2). For every original variable $x_i$ constrained with $v_j$ the algorithm revises the constraint between $v_j$ and $x_i$. This is done by calling function $Revise$ (line 4). During each revision, for each value $a$ of $D(x_i)$ we look for a tuple in the domain of $v_j$ that supports it. As in AC-2001, we store $currentSupport_{x_i,a,v_j}$: the most recent tuple we have found in $D(v_j)$ that supports value $a$ of variable $x_i$². If this tuple has not been deleted from $D(v_j)$ then we know that $a$ is supported. Otherwise, we look for a new supporting tuple starting from the tuple immediately after $currentSupport_{x_i,a,v_j}$. If no such tuple is found then $a$ is removed from $D(x_i)$ (line 21). In that case, all tuples that include that value are removed from the domains of the dual variables that are constrained with $x_i$ (lines 22-23). If these dual variables are not already in the stack they are added to it³. Then, dual variables are removed from the stack sequentially. For each dual variable $v_j$ that is removed from the stack, the algorithm revises the constraint between $v_j$ and each original variable $x_i$ constrained with $v_j$. 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, $currentSupport_{x_i,a,v_j}$ corresponds to $currentSupport_{x_i,a,c_{v_j}}$ in GAC-2001, i.e. the last tuple in constraint $c_{v_j}$ that supports value $a$ of variable $x_i$. 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.