is found, **LastP C**xi,ai,xk is set accordingly (line 29). If maxRPC3rm is used then the residue **LastAC**xi,ai,xk is also updated, as is **LastP C**xk,ak,xi
(bidirectionality).

If the search for a PC-support fails then FALSE will be returned, ai will be deleted, and xi will be added to L.

## 3.1 Light Maxrpc

Light maxRPC (lmaxRPC) is an approximation of maxRPC that only propagates the loss of AC-supports and not the loss of PC-witnesses [10]. This ensures that the obtained algorithm enforces a consistency property that is at least as strong as AC.

lmaxRPC is a procedurally defined local consistency, meaning that its description is tied to a specific maxRPC algorithm. Light versions of algorithms maxRPC3 and maxRPC3rm, simply noted lmaxRPC3 and lmaxRPC3rm respectively, can be obtained by omitting the call to the *checkPCwit* function (lines 11-14 of Algorithm 1). In a similar way, we can obtain light versions of algorithms maxRPC2 and maxRPCrm.

As already noted in [10], the light versions of different maxRPC algorithms may not be equivalent in terms of the pruning they achieve. To give an example, a brute force algorithm for lmaxRPC that does not use any data structures can achieve more pruning than algorithms lmaxRPC2, lmaxRPC3, and lmaxRPCrm, albeit being much slower in practice. Consider that any of these three algorithms will return TRUE in case **LastP C**xi,ai,xj is valid. However, although **LastP C**xi,ai,xj is valid, it may no longer be a PC-support because the PC-witness in some third variable may have been deleted, and it may be the last one. In a case where LastP Cxi,ai,xj was the last PC-support in xj for value ai, the three advanced algorithms will not delete ai while the brute force one will. This is because it will exhaustively check all values of xj for PC-support, concluding that there is none.

The worst-case time and space complexities of algorithm lmaxRPC2 are the same as maxRPC2. Algorithm lmaxRPCrm has O(n 3d 4) time and O(ed) space complexities, which are lower than those of maxRPCrm. Experiments with random problems using algorithms lmaxRPCrm and maxRPCrm showed that the pruning power of lmaxRPC is only slightly weaker than that of maxRPC [10]. At the same time, it can offer significant gains in run times when used during search. These results were also verified by us through a series of experiments on various problem classes.

## 3.2 Correctness And Complexities

We now prove the correctness of algorithms maxRPC3 and maxRPC3rm and analyze their worst-case time and space complexities.