OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A Microstructure-based Family of Tractable Classes for CSPs

Cooper, Martin C. and Jégou, Philippe and Terrioux, Cyril A Microstructure-based Family of Tractable Classes for CSPs. (2015) In: 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), 31 August 2015 - 4 September 2015 (Cork, Ireland).

(Document in English)

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

Official URL: http://dx.doi.org/10.1007/978-3-319-23219-5_6


The study of tractable classes is an important issue in Artificial Intelligence, especially in Constraint Satisfaction Problems. In this context, the Broken Triangle Property (BTP) is a state-of-the-art microstructure-based tractable class which generalizes well-known and previously-defined tractable classes, notably the set of instances whose constraint graph is a tree. In this paper, we propose to extend and to generalize this class using a more general approach based on a parameter k which is a given constant. To this end, we introduce the k-BTP property (and the class of instances satisfying this property) such that we have 2-BTP = BTP, and for k > 2, k-BTP is a relaxation of BTP in the sense that k-BTP is a subset of (k + 1)-BTP. Moreover, we show that if k-TW is the class of instances having tree-width bounded by a constant k, then k-TW is a subset of (k + 1)-BTP. Concerning tractability, we show that instances satisfying k-BTP and which are strong k-consistent are tractable, that is, can be recognized and solved in polynomial time. We also study the relationship between k-BTP and the approach of Naanaa who proposed a set-theoretical tool, known as the directional rank, to extend tractable classes in a parameterized way. Finally we propose an experimental study of 3-BTP which shows the practical interest of this class, particularly w.r.t. the practical solving of instances satisfying 3-BTP and for other instances, w.r.t. to backdoors based on this tractable class.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in Volume 9255 Lecture Notes in Computer Science ISSN : 0302-9743. ISBN: 978-3-319-23218-8. The original PDF is available at: http://link.springer.com/chapter/10.1007/978-3-319-23219-5_6
HAL Id:hal-01343050
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Other partners > Aix-Marseille Université - AMU (FRANCE)
Other partners > Arts et Métiers ParisTech (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
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 Toulon - UTLN (FRANCE)
Laboratory name:
Deposited On:23 Jun 2016 12:17

Repository Staff Only: item control page