# Improving The Performance Of Maxrpc

Thanasis Balafoutis 1, Anastasia Paparrizou 2, Kostas Stergiou 2, and Toby Walsh 3 1Department of Information and Communication Systems Engineering, University of the Aegean, Greece.

2Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Greece.

3NICTA, University of New South Wales, Australia.

## 1 Abstract

Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that can achieve considerably stronger pruning than arc consistency. However, existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose techniques that can boost the performance of maxRPC algorithms. These include the combined use of two data structures to avoid many redundant constraint checks, and heuristics for the efficient ordering and execution of certain operations. Based on these, we propose two closely related maxRPC algorithms. The first one has optimal O(end3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search.

The second one has O(en2d 4
) time complexity, but a restricted version with O(end4) complexity can be very efficient when used during search. Both algorithms have O(ed) space complexity when used stand-alone. However, the first algorithm has O(end) space complexity when used during search, while the second retains the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a more than viable alternative to arc consistency.

## 1 Introduction

maxRPC is a strong domain filtering consistency for binary constraints introduced in 1997 by Debruyne and Bessiere [5]. maxRPC achieves a stronger level of local consistency than arc consistency (AC), and in [6] it was identified, along with arXiv:1008.5189v1 [cs.AI] 30 Aug 2010