CSP Relations and Arc/Path Consistency

The Simplest Explanation

A binary CSP has variables with domains and relations (allowed tuples) for each constrained pair.

• Relation R_AC = set of pairs (a,c) that satisfy constraint between A and C
• Arc consistent = for every value in every domain, there exists a compatible value in each neighbor's domain
• Path consistent = for every pair of values, there exists a middle value completing the path

Computing Relations from Math Constraints (26T1 Papers)

Domains: $D_A=D_B=D_C=\{1,2,3,4\}$

Example 1: $R_{AC}: A = \text{mod}(2C, 3)$

For each $C$, compute $2C \mod 3$, then find matching $A$:

So $R_{AC} = \{(1,2), (2,1), (2,4)\}$ — matches answer A,B,C.

Example 2: $R_{BA}: B = \text{mod}(3A,4)$ (26T1 AN)

$R_{BA}=\{(3,1),(2,2),(1,3)\}$ — tuples are $(B,A)$ order!

Crucial: Tuple order matches relation name: $R_{AC}$ tuples are $(A,C)$, $R_{BA}$ are $(B,A)$.

Arc Consistency

A CSP is arc consistent iff for every arc $X→Y$, every $x \in D_X$ has some $y \in D_Y$ with $(x,y) \in R_{XY}$.

Check each $x$: if no supporting $y$, delete $x$ from $D_X$ and re-queue neighbors.

Is Our Example Arc-Consistent?

$R_{AC}=\{(1,2),(2,1),(2,4)\}$:

• $A=3$: No support in $R_{AC}$ → Remove 3 from $D_A$
• $A=4$: No support → Remove 4
• $C=3$: No $A$ with $(A,3) \in R_{AC}$ → Remove 3 from $D_C$

After pruning, papers answer: Not arc-consistent (No). After making it arc-consistent, re-check path consistency.

Path Consistency

For every pair $(X,Y)$ and every tuple $(x,y) \in R_{XY}$, there must exist $z \in D_Z$ such that $(x,z) \in R_{XZ}$ and $(z,y) \in R_{ZY}$.

After arc pruning, 26T1 papers find it IS path consistent. Hence solution exists: e.g., $A=2, B=2, C=1$ (AN) or $A=2,B=4,C=1$ (FN).

Constraint Graph

• Nodes = variables, edges = constrained pairs (triangle A-B-C)
• Triangle is cyclic — but path consistency still applies (contrary to distractor "does not apply because cycle").