A BTP-Based Family of Variable Elimination Rules for Binary CSPs

Achref El MouelhiAAAI 2017 · DOI

Introduction

Constraint Satisfaction Problems (CSPs) involve finding assignments for a set of variables that satisfy specific constraints. While generally NP-complete, identifying "tractable classes"—subsets of CSPs solvable in polynomial time—is a primary goal in AI research. A prominent concept in this domain is the Broken-Triangle Property (BTP). A CSP lacking "broken triangles" is efficiently solvable. However, standard BTP is often too restrictive for real-world applications.

Figure 1: Illustration of a broken triangle (a) and its resolution (b) within the standard BTP framework.

Previous attempts to generalize BTP have often introduced a trade-off: they allowed for either value merging (reducing domain size) or variable elimination (reducing problem size), but rarely both. Furthermore, many extensions required computationally expensive high-level consistency checks. This paper introduces $m$-fBTP (flexible broken-triangle property), a framework that permits both reduction operations while remaining solvable via simple arc consistency.

The $m$-fBTP Framework

The core innovation of $m$-fBTP lies in the introduction of "support variables." In a standard broken triangle, two values for a variable $x_k$ are incompatible with values in other variables $x_i$ and $x_j$, creating a logical gap. In the $m$-fBTP framework, a broken triangle is considered "flexible" if there exists a set of up to $m$ other variables that "support" it.

Figure 6: The $m$-fBTP property demonstrated with multiple support variables $x_{l_\gamma}$ and $x_{l_\beta}$.

Specifically, for every partial solution of these support variables, there must be at least one value that is incompatible with both $v_i$ and $v_j$ simultaneously. This flexibility ensures that eliminating the variable does not introduce new, unsolvable cliques, preserving the problem's satisfiability.

Theoretical Contributions and Tractability

The paper establishes several key theoretical results regarding the $m$-fBTP class:

  1. Variable Elimination: Variables satisfying $m$-fBTP can be removed without altering the existence of a solution for the overall problem. Theorems 1 and 4 confirm that $m$-fBTP defines the largest tractable class that can be resolved specifically through variable elimination.
  2. Tractability via Arc Consistency: A significant finding is that $m$-fBTP is "conservative"—it remains valid even after filtering values from domains. Consequently, standard arc consistency (Theorem 3) is sufficient to decide satisfiability for any binary CSP satisfying $m$-fBTP relative to a specific variable ordering.
  3. Maximality: The author proves that $(n-3)$-fBTP represents a maximal condition for variable elimination, defining the theoretical limit for simplifying binary CSPs using this logic.
  4. Hierarchy of Properties: The research places $m$-fBTP within the broader landscape of BTP variants. While $m$-fBTP is a subset of $m$-wBTP (weak BTP), it is incomparable to other variants like $k$-BTP or WBTP, indicating it captures a unique set of tractable instances.

Conclusion and Future Directions

While $m$-fBTP provides a powerful tool for CSP simplification, several challenges remain. The property's effectiveness depends on a specific variable ordering; finding an optimal ordering in polynomial time is an ongoing research question. Additionally, this work is currently limited to binary CSPs. Generalizing these "flexible" rules to $n$-ary CSPs represents a promising avenue for future study. Finally, as this research is purely theoretical, empirical evaluation of the overhead involved in checking for $m$-fBTP versus the computational gains from variable elimination would be valuable for practical solver implementation.

Summary updated

BibTeX
@inproceedings{mouelhi2017btp,
  author = {Achref El Mouelhi},
  title = {{A BTP-Based Family of Variable Elimination Rules for Binary CSPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11126},
}
Figure