### 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 .

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