Proof: The proof is very similar to the corresponding proof for maxRPC3. As explained, the main difference between the two algorithms concerns the use of the **LastAC** and **LastP C** structures. As maxRPC3rm does not maintain these structures incrementally, the searches for PC-supports in *searchPCsup* and *checkPCwit* and the searches for PC-witnesses in *searchPCwit* and *checkPCwit* start from scratch. Clearly, this has no effect on the soundness or completeness of the algorithm since it guarantees that all potential PC-supports and PC-witnesses are checked. Furthermore, the conditions for avoiding redundant searches using residues are the same as in maxRPC3. Finally, another difference between the two algorithms is the exploitation of bidirectionality by maxRPC3rm. By the definition of path and arc consistency, bidirectionality holds. That is, when a PC-support
(AC-support) aj ∈ D(xj ) is located for a value ai ∈ D(xi) then aiis a PC-support
(AC-support) for aj . Since the property of bidirectionality is exploited only to update residues, it does not affect the correctness of the algorithm.

We now discuss the complexities of algorithms maxRPC3 and maxRPC3rm and their light versions. To directly compare with existing algorithms for
(l)maxRPC, the time complexities give the asymptotic number of constraint checks3.

Folllowing [9], the *node* time (resp. space) complexity of a (l)maxRPC algorithm is the worst-case time (resp. space) complexity of invoking the algorithm after a variable assignment. The corresponding *branch* complexities of an (l)maxRPC
algorithm are the worst-case complexities of any incremental sequence of k ≤ n invocations of the algorithm. That is, the complexities of incrementally running the algorithm down a branch of the search tree until a fail occurs.

Proposition 3 The node and branch time complexity of (l)maxRPC3is O(end3).

Proof: The complexity is determined by the total number of calls to function isConsistent in searchPCsup, *checkPCwit*, and mainly *searchPCwit* where most checks are executed.

Each variable can be inserted and extracted from L every time a value is deleted from its domain, giving O(d) times in the worst case. Each time a variable xj is extracted from L, *searchPCsup* will look for a PC-support in D(xj ) for all values ai ∈ D(xi), s.t. ci,j ∈ C. For each variable xi, O(d) values are checked. Checking if a value aj ∈ D(xj ) is a PC-support involves first checking in O(1) if it is an AC-support (line 9 in *searchPCsup*) and then calling *searchPCwit*. The cost of 3However, constraint checks do not always reflect run times as other operations may have an equal or even greater effect.