Arc-Consistency and Arc-Consistency Again

Christian Bessière, Marie-Odile CordierAAAI 1993

Introduction

This classic 1993 paper from the AAAI proceedings introduces AC-6, an algorithm that fundamentally improved how we handle "arc-consistency" in constraint satisfaction problems. It effectively bridged the gap between theoretical optimality and practical performance.

AC-6 is the "Goldilocks" of arc-consistency algorithms: it maintains the optimal worst-case time complexity of its predecessor (AC-4) while matching the superior space efficiency and average-case performance of older, non-optimal methods (AC-3). By shifting from "counting all supports" to "finding the next support only when needed," AC-6 became a landmark tool for solving complex constraint networks.

The Arc-Consistency Problem

In Artificial Intelligence, many problems—from scheduling and circuit design to natural language parsing—are modeled as Constraint Networks. These networks consist of variables, domains (possible values for those variables), and constraints (rules about which values can go together).

Because finding a global solution is NP-complete, researchers use "consistency techniques" to prune the search space. Arc-consistency is the most popular: it removes values from a variable's domain that can never be part of a solution because they lack "support" from neighboring variables. Before this paper, engineers faced a dilemma:

  1. AC-3: Fast on average and memory-efficient, but had a non-optimal worst-case time complexity.
  2. AC-4: Theoretically optimal in worst-case time ($O(ed^2)$), but it was a memory hog ($O(ed^2)$ space) and performed poorly on average because it did massive amounts of unnecessary work during initialization.

Methodology: The AC-6 Algorithm

The authors introduced AC-6, which changes the fundamental strategy for verifying if a value is "viable."

  • The "Lazy" Support Strategy: While AC-4 works by pre-calculating and counting every possible support for every value, AC-6 only looks for one support per constraint.
  • Total Ordering: AC-6 assumes a fixed ordering of values in each domain. It finds the first (smallest) support for a value.
  • On-Demand Searching: AC-6 only looks for a new support if the current one is deleted from the domain during the pruning process. Because of the total ordering, it doesn't need to restart the search from the beginning; it just picks up where it left off.
  • Data Structures: It uses a table $M$ to track current domain members and a list $S_{jb}$ to track which values currently rely on value $b$ as their support.

Experimental Benchmarks

The authors evaluated AC-6 against AC-3 and AC-4 using three distinct benchmarks:

  1. The Zebra Problem: A classic logic puzzle involving five houses with various attributes.
  2. The $n$-Queens Problem: A standard scaling test where $n$ queens must be placed on an $n \times n$ chessboard such that no two attack each other.
  3. Randomly Generated Constraint Networks: Thousands of networks were generated, varying parameters like the number of variables ($n$), domain size ($d$), constraint density ($pc$), and constraint tightness ($pu$).

Key Insights

  • "One is Enough": The core "aha moment" is realizing that to prove a value is viable, you don't need to know all the reasons why; you just need to know that at least one reason exists.
  • Space Complexity Breakthrough: By only storing the current support rather than all supports, AC-6 reduces space complexity from $O(ed^2)$ to $O(ed)$. This makes it viable for problems with large domains where AC-4 would crash due to memory limits.
  • Efficiency in "Weak" Constraints: In problems where many values are compatible, AC-4 wastes time cataloging thousands of supports. AC-6 stops after finding the first one, leading to massive speedups.

Results

  • Zebra Problem: AC-6 required only 1,998 operations/tests, compared to 3,824 for AC-4 and 4,008 for AC-3.
  • $n$-Queens: As $n$ increased, the performance gap widened significantly. For 12 queens, AC-4 required nearly 16,000 operations, while AC-6 stayed well under 4,000.
Performance comparison on the n-Queens problem
  • Random Networks: AC-6 consistently outperformed both predecessors across almost all levels of constraint tightness and domain size. It proved particularly robust in "middle-ground" constraints where AC-3 typically struggles.
Performance on random constraint networks (n=10, d=14, pc=70%)

Limitations and Future Work

  • Semantic Knowledge: AC-6 treats constraints as "black boxes." Specialized algorithms could be faster if the mathematical nature of a constraint is known.
  • Binary Focus: The paper focuses on binary constraints. Extending these "lazy" principles to high-order constraints is a natural next step.
  • Ordering Sensitivity: While the algorithm is efficient, the specific total ordering of domains might influence average-case performance, though it remains robust overall.

Summary updated

BibTeX
@inproceedings{bessiere1993arc,
  author = {Christian Bessière and Marie-Odile Cordier},
  title = {{Arc-Consistency and Arc-Consistency Again}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure