## Definition
A binary constraint $c_{ij}$ between variables $X_i$ and $X_j$ is **arc-consistent** if for every value $a \in D_i$ there exists some value $b \in D_j$ with $(a, b)$ satisfying $c_{ij}$.
**AC-3** (Mackworth, 1977) is the standard algorithm that enforces arc consistency on a [[Constraint Satisfaction Problem]] by removing unsupported values from domains.
## Algorithm
```
queue ← all directed arcs (X_i, X_j) in the CSP
while queue is non-empty:
(X_i, X_j) ← pop queue
if Revise(csp, X_i, X_j):
if D_i is empty: return INCONSISTENT
for each X_k that constrains X_i (k ≠ j):
add (X_k, X_i) to queue
return CONSISTENT
function Revise(csp, X_i, X_j):
revised ← false
for each a in D_i:
if there is no b in D_j with (a, b) satisfying c_{ij}:
remove a from D_i
revised ← true
return revised
```
## What It Does and Doesn't Do
- **Removes locally unsupported values.** Every retained value has at least one consistent partner in every related variable's domain.
- **Does not guarantee a solution exists.** Arc consistency is *necessary* but not *sufficient* for satisfiability of a CSP.
- **Solves tree-structured CSPs in polynomial time.** For CSPs whose constraint graph is a tree, AC-3 plus a topological-order assignment finds a solution if one exists.
## Complexity
$O(c \cdot d^3)$ where $c$ is the number of binary constraints and $d$ is the maximum domain size.
## Use Inside Backtracking
AC-3 is most useful **interleaved with [[Backtracking Search]]**:
- After each variable assignment, run AC-3 on the remaining variables.
- If any domain wipes out, backtrack immediately — without committing to further assignments.
- This is called **MAC (Maintaining Arc Consistency)**.
MAC dramatically reduces the number of nodes backtracking explores on hard CSPs.
## Stronger Forms
- **AC-4** — faster in some cases (lazy support sets).
- **k-consistency** — generalises to $k$-tuple consistency. AC = 2-consistency. Higher $k$ is more expensive.
- **Path consistency** — 3-consistency; useful but rarely worth the cost.
- **Generalised arc consistency (GAC)** — extends AC to non-binary constraints; standard for global constraints.
## Related
- [[Constraint Satisfaction Problem]]
- [[Backtracking Search]]
- [[Constraint Propagation]]