On the Minimality and Decomposability of Constraint Networks

Peter van BeekAAAI 1992

Introduction

Constraint Satisfaction Problems (CSPs) are a cornerstone of artificial intelligence, used to model diverse tasks such as scheduling, temporal reasoning, and natural language parsing. However, solving these networks is generally NP-complete, often requiring exhaustive backtracking search that scales exponentially with the number of variables. In his 1992 paper, Peter van Beek identifies a specific geometric property of constraints—row convexity—that allows researchers to bypass this complexity, transforming these difficult tasks into polynomial-time operations.

The Problem: Local vs. Global Consistency

In a constraint network, we typically seek two goals: finding a valid solution (an assignment of values to variables) and finding the "minimal" network (the most explicit representation where every permitted local pair is part of a global solution). While algorithms like path consistency can establish local consistency in $O(n^3)$ time, they do not generally guarantee a global solution or minimality. Van Beek’s research addresses the fundamental question: Under what conditions does local consistency guarantee global consistency?

Methods and the Row Convexity Property

The core of the paper's approach lies in the representation of binary constraints as (0,1)-matrices. In this framework, a '1' indicates a permitted pair of values between two variables, while a '0' indicates a forbidden one.

Defining Row Convexity

A matrix is defined as row convex if, in every row, all the '1's appear consecutively without any intervening '0's.

Constraint matrices for an ambiguous sentence parsing task, showing how complex linguistic constraints can be represented and solved efficiently.

Van Beek proves that if a network is path-consistent and its constraints are row convex, the network is decomposable. This means a solution can be found using a simple, non-backtracking algorithm called INSTANTIATE(R) in $O(dn^2)$ time, where $n$ is the number of variables and $d$ is the domain size.

Crucially, a constraint that is not initially row convex might become so through a reordering of the variable domains. The paper notes that testing whether a matrix can be permuted to satisfy the "consecutive ones property" is efficient, costing only $O(m+n+f)$ using the Booth and Lueker algorithm.

Key Results and Applications

The theoretical insights are validated against several complex problem classes, most notably in natural language processing and computer vision.

Backtrack-Free Parsing

A significant result involves the parsing of ambiguous sentences. Previous methods for certain 11-word sentences required backtracking search. Van Beek demonstrates that by representing these as constraint networks and ensuring row convexity through domain ordering, the problem can be solved with zero backtracking.

Constraint matrices for an ambiguous sentence parsing task, showing how complex linguistic constraints can be represented and solved efficiently.

Complexity Gains

For networks satisfying these properties, the total time to find both the minimal network and a solution is $O(\max(dn^2, n^3))$. This represents a massive improvement over the exponential search typically required for NP-complete problems.

Conclusion and Future Work

Van Beek’s work establishes row convexity as the "missing link" that makes local path consistency equivalent to global decomposability. While the paper focuses on binary constraints, it lays the groundwork for identifying tractable subclasses of CSPs. The author also conjectures that constraint networks in computer vision—specifically those arising from "orthohedral scenes" (objects with right angles)—are naturally row convex after path consistency, a promising avenue for future research in automated scene labeling.

Summary updated

BibTeX
@inproceedings{beek1992minimality,
  author = {Peter van Beek},
  title = {{On the Minimality and Decomposability of Constraint Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure