On Broken Triangles

Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux, Bruno ZanuttiniIJCAI 2016

Introduction

Constraint Satisfaction Problems (CSPs) are a cornerstone of artificial intelligence, used to model everything from scheduling and planning to graph coloring and radio frequency assignment. However, because CSPs are generally NP-hard, researchers are constantly seeking ways to simplify them. This research introduces BTP-merging, a novel reduction technique that shrinks problem size by merging domain values rather than simply deleting them. By generalizing the "Broken Triangle Property" (BTP) from binary to general-arity constraints, the authors provide both a practical preprocessing tool and a new theoretical class of problems solvable in polynomial time.

The Broken Triangle Property and Merging

The Broken Triangle Property (BTP) was originally identified as a condition that defines a tractable class for binary CSPs—those where constraints involve only two variables. A "broken triangle" is a specific conflicting pattern between values across three variables. While instances that globally satisfy BTP are rare in practice, the authors propose using the property locally as a reduction rule.

Unlike standard reduction techniques like Arc Consistency, which delete inconsistent values, BTP-merging identifies two values ($a$ and $b$) for a variable that are "BT-free." This means they do not participate in any broken triangle patterns with other variables. If two values are BT-free, they can be merged into a single new value ($c$) without changing the satisfiability of the overall problem. This process is illustrated in the figures below:

Figure 1: Initial configuration of a CSP where variable x contains two values, a and b, which are candidates for merging.
Figure 2: The resulting state after the BTP-merge operation, where values a and b are replaced by a single value c, simplifying the domain.

This merging rule is proven to preserve satisfiability, and any solution found for the simplified problem can be reconstructed for the original instance in linear time.

Generalizing to Higher Arity

A major contribution of this work is the extension of BTP to "general-arity" CSPs, where constraints can involve any number of variables. The authors define GABT (General-Arity Broken Triangle) to handle these complex constraints. Furthermore, they introduce Directional BTP (DGABTP), a version of the property that depends on a specific variable ordering. They prove that if an instance satisfies DGABTP for a known ordering, it can be solved in polynomial time. This successfully extends the BTP tractable class to a much broader set of problems.

Key Insights and Theoretical Strengths

  • Superiority over Substitution: BTP-merging is shown to be strictly more powerful than "neighborhood substitution," a classic CSP reduction technique.
  • The Cascade Effect: Merging two values at one variable can eliminate broken triangles at a different variable. This can trigger a "cascade" of further reductions that were not possible in the initial state.
  • Complexity of Ordering: While solving a DGABTP instance is fast if the variable order is known, the authors proved that finding whether such an order exists is itself NP-complete. This suggests that while the property is theoretically powerful, practical applications must rely on heuristics to find effective orderings.

Experimental Results

The authors evaluated BTP-merging using 3,811 benchmark instances from the International CP Competition (CPAI08), covering domains like scheduling (jobShop), graph coloring (gr-col), and academic puzzles (hanoi, pigeons).

The results demonstrated significant domain reduction in specific categories. For example, in the marc domain, 98% of values were either deleted or merged. In scheduling tasks (os-taillard), they achieved a 62% reduction. Across several other categories, the method consistently reduced variable-value assignments by over 40%.

Limitations and Future Work

Despite its success in specific domains, BTP-merging is not a universal solution. On a large set of general benchmarks, the reduction was as low as 0.02%, indicating that the technique is highly sensitive to problem structure. Additionally, the computational overhead of identifying mergeable pairs can be high. Future research will likely focus on more efficient algorithms to target instances where merges are most likely to occur and developing heuristics to find "good enough" variable orderings for the directional property.

Summary updated

BibTeX
@inproceedings{cooper2016broken,
  author = {Martin C. Cooper and Achref El Mouelhi and Cyril Terrioux and Bruno Zanuttini},
  title = {{On Broken Triangles}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure