### Citation

(PDF)
Peter van Beek and Rina Dechter.
On the minimality and global consistency of
row-convex constraint networks.
*J. ACM*,
42:543-561, 1995.

### Abstract

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 that a network is both minimal and
globally consistent.
Globally consistent networks have the property that a solution can be
found without backtracking.
We show that one can test for the row convexity property
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 class of binary constraint
networks for which we can solve both tasks (i) and (ii)
efficiently.
Finally, we generalize the results for binary constraint networks
to networks with non-binary constraints.

**Return to Publications**