Detecting and Exploiting Subproblem Tractability

Christian Bessière 1 Clément Carbonnel 1 Emmanuel Hébrard 2 George Katsirelos 3 Toby Walsh 4, 5
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 LAAS-MOGISA
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
3 MIAT INRA - Unité de Mathématiques et Informatique Appliquées de Toulouse
4 NICTA - National ICT Australia [Sydney]
5 School of Computer Science and Engineering [Sydney]
Abstract : Constraint satisfaction problems may be nearly tractable. For instance, most of the relations in a problem might belong to a tractable language. We introduce a method to take advantage of this fact by computing a backdoor to this tractable language. The method can be applied to many tractable classes for which the membership test is itself tractable. We introduce therefore two polynomial membership testing algorithms, to check if a language is closed under a majority or conservative Mal'tsev polymorphism, respectively. Then we show that computing a minimal backdoor for such classes is fixed parameter tractable (FPT) if the tractable subset of relations is given, and W[2]- complete otherwise. Finally, we report experimental results on the XCSP benchmark set. We identi- fied a few promising problem classes where prob- lems were nearly closed under a majority polymorphism and small backdoors could be computed.
Keywords : Backdoor Fixed Parameter Tractability Tractability Polymorphism
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. 23rd International Joint Conference on Artificial Intelligence, pp.468-474, 2013, 〈http://ijcai-13.org〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830330
Contributeur : Joël Quinqueton <>
Soumis le : mardi 4 juin 2013 - 16:58:40
Dernière modification le : samedi 27 octobre 2018 - 01:25:27
Document(s) archivé(s) le : mardi 4 avril 2017 - 16:52:28

Fichier

ijcai13-tractability.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00830330, version 1

Collections

LAAS-ROC | LAAS | INRA | UNIV-TLSE3 | COCONUT | LIRMM | INSA-TOULOUSE | MIPS | UNIV-MONTPELLIER

Citation

Christian Bessière, Clément Carbonnel, Emmanuel Hébrard, George Katsirelos, Toby Walsh. Detecting and Exploiting Subproblem Tractability. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. 23rd International Joint Conference on Artificial Intelligence, pp.468-474, 2013, 〈http://ijcai-13.org〉. 〈lirmm-00830330〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

451

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD