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.

**Proof:**
We assume that for any constraint in the dual encoding, the
non-binary constraints corresponding to the two dual variables
and share at most original variables
of domain size . This means that each piecewise
decomposition consists of at most groups. Obviously, is
equal to , where 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 and
, we iterate over all the tuples in . This is done
with asymptotic time complexity. Then, all empty
groups are inserted in (lines 7-11). This requires
operations in the worst case. After the initialization, function
is called. A group is inserted to (and later
removed) only when it becomes empty. This means that the **
while** loop of is executed at most times for
each constraint, and at most times in total. This is also
the maximum number of times function is called (once in
every iteration of the loop). The cost of function is
computed as follows: Assuming is called for a group
, we iterate over the (at most) tuples
of group
(line 20). In each iteration we
remove a tuple (line 21) and we update the counters of the
groups where belongs (lines 22-23). There are at most
such groups (in case is constrained with all other dual
variables). Therefore, each iteration costs , and as a
result, each call to costs . Since
is called at most times, the complexity of PW-AC,
including the initialization step, is
=.

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 space need to store the allowed tuples of the non-binary constraints. Algorithm PW-AC also requires space to store the counters for all the groups, space for the stack, and space for the fast implementation of function .

<994>>

Nikolaos Samaras 2005-11-09