On the Minimality and Decomposability of Constraint Networks

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Constraint Satisfaction

Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known to be NP-complete in the general case. Task (i) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraints called row convexity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee a network is both minimal and decomposable. Decomposable networks have the property that a solution can be found without backtracking. We show that the row convexity property can be tested for efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a large class of constraint networks for which we can solve both tasks (i) and (ii) efficiently.