ON THE MINIMALITY AND GLOBAL CONSISTENCY OF ROW-CONVEX CONSTRAINT NETWORKS

Constraint networks have been shown to be useful in formulating such d iverse problems as scene labeling, natural language parsing, and tempo ral reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the correspondi ng minimal network where the constraints are as explicit as possible. Both tasks are known to be NP-complete in the general case. Task (i) i s usually solved using a backtracking algorithm, and task (ii) is ofte n solved only approximately by enforcing various levels of local consi stency. In this paper, we identify a property of binary constraints ca lled row convexity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee t hat a network is both minimal and globally consistent. Globally consis tent networks have the property that a solution can be found without b acktracking. We show that one can test for the row convexity property efficiently and we show, by examining applications of constraint netwo rks discussed in the literature, that our results are useful in practi ce. Thus, we identify a class of binary constraint networks for which we can solve both tasks (i) and (ii) efficiently. Finally, we generali ze the results for binary constraint networks to networks with nonbina ry constraints.