On the Consistency of General Constraint-Satisfaction Problems

Philippe JégouAAAI 1993

Abstract

This paper bridges a major gap in constraint satisfaction theory by extending Freuder’s classic results for binary constraints to general, n-ary constraints. It introduces the concepts of hyper-k-consistency and hypergraph width, providing a formal theorem that guarantees when a complex, cyclic problem can be solved without backtracking.

Introduction

Constraint-Satisfaction Problems (CSPs)—such as map coloring, scheduling, or database querying—are fundamentally NP-complete. To avoid the "combinatorial explosion" of backtracking search, researchers use consistency techniques to prune the search space. Historically, theoretical guarantees for solving CSPs were split into two camps: binary CSPs, where connectivity and local consistency were well-understood for two-variable constraints, and n-ary CSPs in database theory, which were largely restricted to acyclic networks.

This research tackles the "missing middle": providing global consistency guarantees for general (n-ary) CSPs that contain cycles. By shifting the focus from individual variables to the relationships between constraints, the paper establishes a unifying theory for constraint satisfaction.

Generalizing Consistency to Hypergraphs

The author introduces two novel definitions to generalize existing graph theory to hypergraphs, where "edges" or constraints can connect any number of variables:

  • Hyper-k-consistency: While standard k-consistency looks at sets of variables, hyper-k-consistency ensures that any consistent assignment across $k-1$ constraints can be extended to a $k$-th constraint. This is a generalization of "inter-consistency" used in relational databases.
  • Width of a Hypergraph: This structural measure quantifies the connectivity or "thickness" of a hypergraph. By ordering the constraints and counting the maximal intersections each constraint has with its predecessors, we obtain a measure of the problem's topological complexity.
Figure 1: A hypergraph representation of constraints (left) alongside its associated graph structures (middle, right) used to calculate structural width.

Global Consistency Guarantees

The core of the paper is a formal proof (Theorem 14) showing that if a CSP’s local consistency level is higher than its hypergraph width, the problem is globally consistent. This means a solution can be found in polynomial time without ever hitting a dead end during search. Specifically, a CSP is globally consistent if it is strongly hyper-k-consistent and its hypergraph width $L(H)$ is less than or equal to $k-1$.

This theorem unifies previous work, showing that Freuder’s famous 1982 theorem for binary constraints is a special case of this broader result. For standard binary CSPs, "strong hyper-3-consistency" is sufficient to guarantee a solution because the width of a standard graph is at most 2.

Discussion and Limitations

While theoretically powerful, the practical application of this theorem involves several trade-offs:

  • Complexity: Achieving hyper-k-consistency is polynomial in terms of the number of constraints but scales exponentially with $k$ ($O(r^k)$, where $r$ is the size of the relations).
  • Structural Dynamics: The process of achieving consistency (filtering) can add new constraints, which may change the hypergraph's width and invalidate initial structural analysis.
  • Optimization: Determining the minimum width of a hypergraph (finding the best constraint ordering) is likely an NP-hard problem, suggesting that heuristics are necessary for real-world application.

Conclusion

This work reinforces the deep link between the topology (shape) of a network and the semantics (nature) of its constraints. By providing a structural measure for n-ary problems, it offers a foundation for identifying new polynomial classes of real-world problems that can be solved efficiently through local consistency techniques.

Summary updated

BibTeX
@inproceedings{jegou1993consistency,
  author = {Philippe Jégou},
  title = {{On the Consistency of General Constraint-Satisfaction Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure