On the minimality and decomposability of constraint networks
Peter van Beek · 1992
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 ...