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.
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.
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:
- 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.
- 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.
- 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.
- 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