The Extendable-Triple Property: A New CSP Tractable Class beyond BTP

Philippe Jégou, Cyril TerriouxAAAI 2015 · DOI

Abstract

Constraint Satisfaction Problems (CSPs) are generally NP-complete, posing significant challenges for real-world applications. This paper introduces the Extendable-Triple Property (ETP), a new "island of tractability" that generalizes the well-known Broken Triangle Property (BTP). ETP identifies a broader class of complex problems that can be solved in polynomial time using standard, off-the-shelf solvers like MAC or RFL. Empirical analysis on 2,260 benchmarks demonstrates that ETP is more prevalent than BTP in practice and helps explain the efficiency of modern solvers through the "backdoor" effect.

Introduction

Constraint Satisfaction Problems (CSPs) serve as the mathematical foundation for diverse tasks such as scheduling, frequency assignment, and hardware verification. Due to their NP-complete nature, researchers focus on identifying "tractable classes"—subsets of CSPs guaranteed to be solvable in polynomial time.

The Broken Triangle Property (BTP) represented a significant advancement as a "hybrid" tractable class, considering both constraint structure and specific value assignments. However, BTP's strict requirements limit its applicability. This research introduces the Extendable-Triple Property (ETP) to relax these constraints, capturing a wider array of solvable instances while maintaining compatibility with standard backtracking algorithms.

The Extendable-Triple Property

ETP generalizes BTP by being more permissive regarding local patterns of incompatibility. While BTP forbids specific "broken triangle" configurations among triples of variables, ETP allows certain broken triangles to exist, provided they do not prevent a consistent assignment from being extended to subsequent variables in a given ordering.

Visual representation of the Broken Triangle Property (BTP) and its extensions.

Theoretical Foundations

The authors establish several key properties of ETP:

  1. Generalization: Mathematically, $BTP \subsetneq ETP$. Every problem satisfying BTP also satisfies ETP, but the converse is not true.
  2. Strong Path-Consistency (SPC): If a CSP satisfies ETP and is preprocessed to be Strongly Path-Consistent—ensuring local consistency among triples—it is guaranteed to be solvable in polynomial time.
  3. Solver Compatibility: Standard algorithms like MAC (Maintaining Arc Consistency) and RFL (Real Full Look-ahead) naturally solve ETP-SPC instances without modification.
  4. Recognition: A polynomial-time algorithm ($O(n^3 d^4)$) can determine if a CSP can be ordered to satisfy ETP.

Empirical Evaluation

The property was evaluated against a library of 2,260 binary benchmarks from the CSP 2008 Competition, spanning academic, random, and real-world instances.

Table showing the number of variables (backdoor size) that must be assigned to reach a tractable sub-problem for various benchmark instances.

Key Results

  • Prevalence: ETP appeared more frequently than BTP in raw benchmarks (41 vs. 13 instances). With standard Arc Consistency (AC) filtering, 50 instances were ETP; adding SPC increased this to 76.
  • The "Backdoor" Effect: The study found that many difficult instances become ETP-tractable after a solver assigns only a small fraction of "backdoor" variables. For example, in the 2-insertions-3-4 instance, assigning just 1 out of 37 variables makes the remaining problem ETP-tractable.
  • Real-World Utility: ETP was identified in practical competition benchmarks, such as frequency assignment (fapp) and crossword instances, proving its relevance beyond theoretical models.

Discussion and Future Work

ETP offers a powerful tool for understanding solver performance on complex benchmarks. However, the reliance on Strong Path-Consistency (SPC) is a limitation, as SPC can be computationally expensive for very large problems.

Future research will explore:

  • Relaxed Consistency: Determining if weaker forms of consistency, such as directional path consistency, suffice for ETP tractability.
  • Higher Arity: Extending ETP from binary to n-ary constraints.
  • Automated Ordering: Optimizing algorithms to find the variable orderings required for ETP.

Summary updated

BibTeX
@inproceedings{jegou2015extendable,
  author = {Philippe Jégou and Cyril Terrioux},
  title = {{The Extendable-Triple Property: A New CSP Tractable Class beyond BTP}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9754},
}
Figure