---
title: "A Study of Residual Supports in Arc Consistency"
authors:
  - "Christophe Lecoutre"
  - "Fred Hemery"
doi: ""
url: "https://ijcai.org/proceedings/2007/18"
pdf: "https://ijcai.org/proceedings/2007/0018.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "125-129"
track: ""
keywords:
---

# A Study of Residual Supports in Arc Consistency

Christophe Lecoutre, Fred Hemery

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 125-129.

## Abstract

In an Arc Consistency (AC) algorithm, a residual support, or residue, is a support that has been stored during a previous execution of the procedure which determines if a value is supported by a constraint. The point is that a residue is not guaranteed to represent a lower bound of the smallest current support of a value. In this paper, we study the theoretical impact of exploiting residues with respect to the basic algorithm AC3. First, we prove that AC3rm (AC3 with multi-directional residues) is optimal for low and high constraint tightness. Second, we show that when AC has to be maintained during a backtracking search, MAC2001 presents, with respect to MAC3rm, an overhead in O(med) per branch of the binary tree built by MAC, where m denotes the number of refutations of the branch, e the number of constraints and d the greatest domain size of the constraint network. One consequence is that MAC3rm admits a better worst-case time complexity than MAC2001 for a branch involving m refutations when either m > d^2 or m > d and the tightness of any constraint is either low or high. Our experimental results clearly show that exploiting residues allows enhancing MAC and SAC algorithms.