ALCOMFT-TR-03-33

Klaus Meer
On consistency and width notions for constraint programs with algebraic constraints
Århus. Work package 4. September 2003.

Abstract: Width notions have been studied in the framework of constraint satisfaction problems in order to exhibit subclasses of problems which allow backtrack-free solution algorithms. Among the most prominent such notions is the tree-width of the constraint graph studied, for example, by Freuder. However, Freuder's results heavily rely on constraint programs over finite domains, where each constraint is given as a list of admissible tuples and therefore fails, for example, if continuous domains are considered. Faltings introduced an arc consistency notion for constraints over continuous domains that are given in a more complicated form using formulas c(x,y) >= 0 for continuously differentiable functions c. He then showed for such binary constraints how arc consistency can be established and guarantees solvability of tree-structured problems.

In this paper we want to study a generalization of Freuder's and Faltings' notions to problems with algebraic constraints. We show that an analog notion of k-consistency guarantees backtrack-free solution algorithms for tree-structured problems, but argue that already for binary constraints and a tree as structure of the constraint graph there arise unavoidable complexity problems in achieving k-consistency. We then propose a new width notion, based on the work of Makowsky and Meer, which in certain situations even allows to include global constraints without yielding a complexity explosion - something not true within the above mentioned setting.

Postscript file: ALCOMFT-TR-03-33.ps.gz (97 kb).