Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems

Philippe JégouAAAI 1993

This 1993 paper from the AAAI proceedings introduces a novel way to break down hard Constraint-Satisfaction Problems (CSPs) by looking "under the hood" at the relationships between specific values, rather than just the variables themselves.

TL;DR

While traditional CSP decomposition methods fail when variables are highly interconnected, this paper proposes a method based on the micro-structure of the problem. By triangulating a graph of compatible variable-value pairs, the authors can decompose a single NP-complete problem into a collection of smaller sub-problems that are often significantly easier—or even polynomial—to solve.

What Problem Does This Paper Address?

Constraint-Satisfaction Problems (like map coloring or scheduling) are generally NP-complete. To speed them up, researchers usually look at the "constraint graph"—a map of which variables are linked by constraints. If this graph looks like a tree or has a simple structure, we can use "tree-clustering" or "cycle-cutset" methods to solve the problem efficiently.

However, these traditional methods hit a wall when the constraint graph is dense. If every variable is constrained by every other variable (a "complete graph"), the complexity remains $O(d^n)$, where $d$ is the domain size and $n$ is the number of variables. The author addresses this "hard case" by shifting focus from the macro-structure (variables) to the micro-structure (the specific values those variables can take).

Methods

The core of the paper is the definition and manipulation of the micro-structure graph:

  1. The Micro-structure Graph: Instead of nodes representing variables, nodes represent (Variable, Value) pairs. An edge exists between two nodes if those specific values are compatible according to the problem's constraints.
  2. The Clique Property: The author observes that finding a solution to a CSP is mathematically equivalent to finding an $n$-clique (a fully connected subgraph of size $n$) within this micro-structure graph.
  3. Triangulation: Since finding cliques is generally hard, the author suggests triangulating the micro-structure graph. Triangulation involves adding "chord" edges until every cycle of length four or more has a shortcut.
  4. Domain Decomposition: Triangulated graphs have a special property: their maximal cliques can be found in linear time. The author uses these maximal cliques to "filter" the domains of the variables. Each maximal clique induces a sub-problem with smaller domains ($\delta_i$).
  5. Solving: The original problem is solved by solving the collection of these smaller sub-problems.

Datasets

The paper is a theoretical algorithmic contribution and does not use large-scale empirical datasets or modern benchmarks. It uses a small, hand-crafted binary CSP example (Figure 1 and 2) to illustrate the micro-structure and the triangulation process.

Key Insights and Ideas

  • Structural Leverage in Dense Graphs: The most significant insight is that even if a constraint graph is a "clique" at the variable level, the underlying value-level interactions (the micro-structure) might still be sparse or decomposable.
  • Triangulation as a Pre-processor: By applying graph triangulation to the micro-structure, we can identify "islands" of compatibility. If a maximal clique in the triangulated graph doesn't cover all variables, that entire branch of the search space can be discarded immediately.
  • New Polynomial Classes: The author identifies two new classes of CSPs that can be solved in polynomial time:
  • CSPs where the micro-structure is already triangulated.
  • CSPs where the triangulation results in sub-problems where each variable has only 1 or 2 possible values (bivalent domains).

Key Results

  • Complexity Reduction: The complexity shifts from one massive $O(m \cdot d^n)$ problem to a sum of smaller problems: $\sum O(m \cdot \delta_i^n)$, where $\delta_i \le d$.
  • Linear Decomposition: The process of decomposing the domains is linear relative to the size of the micro-structure graph ($n \cdot d$ vertices).
  • Sub-problem Bound: The number of new sub-problems generated is at most linear in the size of the original problem instance.
  • Efficiency: If the decomposition results in very small $\delta_i$ (like 1 or 2), the problem effectively collapses from exponential to polynomial time.

Limitations and Future Work

  • Lack of Empirical Testing: The author explicitly notes that "an experimental analysis must now be realized to see practical interest." The paper proves the theoretical bounds but doesn't show how often real-world problems yield "good" micro-structure decompositions.
  • Binary Constraint Focus: The method is primarily designed for binary CSPs (constraints between two variables). While the author suggests a way to extend this to $n$-ary constraints using primal graphs, the extension is less direct and potentially less efficient.
  • Memory Overhead: Building the micro-structure graph requires $O(n \cdot d)$ vertices and potentially $O(n^2 \cdot d^2)$ edges, which could be memory-intensive for problems with very large domains.

Summary updated

BibTeX
@inproceedings{jegou1993decomposition,
  author = {Philippe Jégou},
  title = {{Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure