Complexities

The PW-AC algorithm consists of two phases. In the initialization phase we set up the group counters, and in the main phase we delete unsupported tuples and propagate the deletions. We now analyze the time complexity of PW-AC. Note that in our complexity analysis we measure operations, such as incrementing or decrementing a counter, since PW-AC does not perform consistency checks in the usual sense.

Proposition 4.1   The worst-case time complexity of algorithm PW-AC is $O(e^3d^{k})$.

Proof: We assume that for any constraint in the dual encoding, the non-binary constraints corresponding to the two dual variables $v_i$ and $v_j$ share at most $f$ original variables $x_1,\ldots ,x_f$ of domain size $d$. This means that each piecewise decomposition consists of at most $d^f$ groups. Obviously, $f$ is equal to $k-1$, where $k$ is the maximum arity of the constraints. In the initialization phase of lines 3-6 we iterate over all constraints, and for each constraint between variables $v_i$ and $v_j$, we iterate over all the tuples in $D(v_i)$. This is done with $O(e^2d^k)$ asymptotic time complexity. Then, all empty groups are inserted in $Q$ (lines 7-11). This requires $e^2d^f$ operations in the worst case. After the initialization, function $Propagation$ is called. A group is inserted to $Q$ (and later removed) only when it becomes empty. This means that the while loop of $Propagation$ is executed at most $d^f$ times for each constraint, and at most $e^2d^f$ times in total. This is also the maximum number of times function $Revise$ is called (once in every iteration of the loop). The cost of function $Revise$ is computed as follows: Assuming $Revise$ is called for a group $s_{l}(v_i,v_j)$, we iterate over the (at most) $d^{k-f}$ tuples of group $sup(s_{l}(v_i,v_j))$ (line 20). In each iteration we remove a tuple $\tau$ (line 21) and we update the counters of the groups where $\tau$ belongs (lines 22-23). There are at most $e$ such groups (in case $v_j$ is constrained with all other dual variables). Therefore, each iteration costs $O(e)$, and as a result, each call to $Revise$ costs $O(ed^{k-f})$. Since $Revise$ is called at most $e^2d^f$ times, the complexity of PW-AC, including the initialization step, is $O(e^2d^{k}+e^2d^{f}+e^2d^fed^{k-f})$=$O(e^3d^{k})$. $\Box$

Note that PW-AC can be easily used incrementally during search. In this case, the initialization phase will only be executed once. The asymptotic space complexity of PW-AC, and any AC algorithm on a binary encoding, is dominated by the $O(ed^k)$ space need to store the allowed tuples of the non-binary constraints. Algorithm PW-AC also requires $O(e^2d^f)$ space to store the counters for all the groups, $O(e^2d^f)$ space for the stack, and $O(fe^2)$ space for the fast implementation of function $GroupOf$.

<994>>