OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Broken Triangles: From Value Merging to a Tractable Class of General-Arity Constraint Satisfaction Problems

Cooper, Martin C. and Duchein, Aymeric and El Mouelhi, Achref and Escamocher, Guillaume and Terrioux, Cyril and Zanuttini, Bruno Broken Triangles: From Value Merging to a Tractable Class of General-Arity Constraint Satisfaction Problems. (2016) Artificial Intelligence, 234. 196-218. ISSN 0004-3702

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1016/j.artint.2016.02.001


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 arbitrary instances of binary CSP, thus providing a novel polynomial-time reduction operation. Extensive 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 with constraints of arbitrary arity and we investigate the theoretical relationship with resolution in SAT. A directional version of general-arity BTP-merging then allows us to extend the BTP tractable class previously defined only for binary CSP. We investigate the complexity of several related problems including the recognition problem for the general-arity BTP class when the variable order is unknown, finding an optimal order in which to apply BTP merges and detecting BTP-merges in the presence of global constraints such as AllDifferent.

Item Type:Article
Additional Information:http://www.sciencedirect.com/science/article/pii/S0004370216300121
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:Other partners > Aix-Marseille Université - AMU (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Ecole Nationale Supérieure d'Ingénieurs de Caen - ENSICAEN (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > University College Cork (IRELAND)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Caen Basse-Normandie (FRANCE)
Other partners > Université de Toulon - UTLN (FRANCE)
Laboratory name:
Deposited On:03 May 2017 08:18

Repository Staff Only: item control page