AbstractConstraint 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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- permutations and combinations; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods -- relation systems
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Consecutive ones property, constraint-based reasoning, constraint networks, constraint satisfaction problems, path consistency, relations, row convexity
Selected papers that cite this one
- Peter van Beek and Rina Dechter. Constraint tightness and looseness versus local and global consistency. Journal of the ACM, 44(4):549-566, July 1997.
- Rina Dechter and Peter van Beek. Local and global relational consistency. Theoretical Computer Science, 173(1):283-308, 20 February 1997.
Selected references
- Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes. Journal of the ACM, 30(3):479-513, July 1983.
- Eugene C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24-32, January 1982.
- Eugene C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4):755-761, October 1985.
- Lefteris M. Kirousis and Christos H. Papadimitriou. The complexity of recognizing polyhedral scenes (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pages 175-185, Portland, Oregon, 21-23 October 1985. IEEE.