Abstract
Acyclic constraint satisfaction problems with arithmetic constraints and domains consisting of sets of disjoint intervals have exponential complexity, since disjunctions of intervals may be introduced while propagating through the constraints. This has prompted many researchers to use approximations on the bounds of sets of intervals, resulting in sound, but incomplete, algorithms. We delineate the complexity of propagation of sets of intervals through arithmetic constraints. For many types of constraint networks, our analysis shows linear, rather than exponential, complexity bounds. Furthermore, exponential complexity is a worst-case scenario that is surprisingly hard to achieve. In some cases, the number of disjoint intervals in the output of an acyclic constraint satisfaction problem is independent of the number of disjoint intervals in the input. Some empirical results are presented, showing that the worst-case bound is not achieved for random intervals.