# Arc Consistency

## Artificial Intelligence Online Tutorials

Suppose we have variable X and Y. A relation r(X,Y) is converted into two arcs <X,r(X,Y)> and <Y,r(X,Y)>. The arc <X,r(X,Y)> is arc consistent if for every element of the domain of X, there is an element of the domain of Y such that r(X,Y) is true. It can be made arc consistent by removing those elements of the domain of X for which there is no corresponding element of the domain of Y.

For example, suppose we have variables A and B with domains {1,2,3,4} and the relation A<B. This can be drawn as a network:

Neither arc is arc consistent. You can click on the left-hand arc (the <A,(A<B)> arc) to make it arc consistent. Note how the domain of A is reduced and the arc turns green. You can click on the right-hand arc (the <B,(A<B)> arc) to make it arc consistent. The domain of B is reduced and the arc turns green. At this stage all arcs are arc consistent, and we say that the network is arc consistent.

In this and the following networks the green arcs are those arcs that are known to be arc consisitent. The blue arcs are those that are not known to be arc consistent. Clicking on a blue arc <X,r(X,Y)> makes it arc consistent by perhaps reducing the domain of X. You can reset the network to see how this works.

Once an arc <X,r(X.Y)> has been made arc consistent, it will remain arc consistent until the domain of Y is reduced. When the domain of Y is reduced, the arc will become blue. This means that the arc needs to be checked; it does not mean that the arc is necessarily not arc consistent.

Consider the following example with four arcs: