---
title: "On Broken Triangles"
authors:
  - "Martin C. Cooper"
  - "Achref El Mouelhi"
  - "Cyril Terrioux"
  - "Bruno Zanuttini"
doi: ""
url: "https://ijcai.org/proceedings/2016/617"
pdf: "https://ijcai.org/proceedings/2016/0617.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "4135-4138"
track: ""
keywords:
---

# On Broken Triangles

Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux, Bruno Zanuttini

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 4135-4138.

## Abstract

A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.