R76  
On the Complexity of IntervalBased Constraint Networks
Rony Shapiro, Yishai A. Feldman, and Rina Dechter (dechter@ics.uci.edu)

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 worstcase 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 worstcase bound is not achieved for random intervals. [ps] [pdf] 