Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination

Abstract

The Constraint Satisfaction Problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a novel tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can also be detected in polynomial time. We show that both the broken-triangle property and its extension can be used to eliminate variables, and that both of these properties provide the basis for preprocessing procedures that yield unique closures orthogonal to value elimination by enforcement of consistency. Finally, we also discuss the possibility of using the broken-triangle property in variable-ordering heuristics.