singleton AC (SAC), as a promising alternative to AC. Although SAC has received considerable attention since, maxRPC has been comparatively overlooked. The basic idea of maxRPC is to delete any value a of a variable x that has no arc consistency (AC) or path consistency (PC) support in a variable y. A value b is an AC
support for a if the two values are compatible, and it is also a PC support for a if this pair of values is path consistent. A pair of values (**a, b**) is path consistent iff for every third variable there exists at least one value, called a PC witness, that is compatible with both a and b.

The first algorithm for maxRPC was proposed in [5], and two more algorithms have been proposed since then [7, 10]. The algorithms of [5] and [10] have been evaluated on random problems only, while the algorithm of [7] has not been experimentally evaluated at all. Despite achieving considerable pruning, existing maxRRC algorithms suffer from overhead and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. These constraint checks occur when a maxRPC algorithm searches for an AC support for a value and when, having located one, it checks if it is also a PC support by looking for PC witnesses in other variables. As a result, the use of maxRRC during search often slows down the search process considerably compared to AC, despite the savings in search tree size.

In this paper we propose techniques to improve the applicability of maxRPC by eliminating some of these redundancies while keeping a low space complexity. We also investigate approximations of maxRPC that only make slightly fewer value deletions in practice, while being significantly faster. We first demonstrate that we can avoid many redundant constraint checks and speed up the search for AC
and PC supports through the careful and combined application of two data structures already used by maxRPC and AC algorithms [7, 10, 2, 8, 9]. Based on this, we propose a coarse-grained maxRPC algorithm called maxRPC3 with optimal O(end3) time complexity. This algorithm displays good performance when used stand-alone (e.g. for preprocessing), but is expensive to apply during search. We then propose another maxRPC algorithm, called maxRPC3rm. This algorithm has O(en2d 4) time complexity, but a restricted version with O(end4) complexity can be very efficient when used during search through the use of *residues*. Both algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while maxRPC3rm retains the O(ed) complexity.

Similar algorithmic improvements can be applied to *light maxRPC* (lmaxRPC),
an approximation of maxRPC [10]. This achieves a lesser level of consistency compared to maxRPC but still stronger than AC, and is more cost-effective than maxRPC when used during search. Experiments confirm that lmaxRPC is indeed a considerably better option than maxRPC.