### Citation

(PDF)
Peter van Beek.
On the minimality and decomposability of constraint networks.
*Proceedings of the 10th National Conference on
Artificial Intelligence,*
San Jose, California, 447-452, July, 1992.

### 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 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.

**Return to Publications**