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 LEO
INRA Toulouse - Institut national de la recherche agronomique [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 poly- nomial membership testing algorithms, to check if a language is closed under a majority or conser- vative 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 experimen- tal results on the XCSP benchmark set. We identi- fied a few promising problem classes where prob- lems were nearly closed under a majority polymor- phism and small backdoors could be computed.
Type de document :
Communication dans un congrès
IJCAI'2013: 23rd International Joint Conference on Artificial Intelligence, 2013, Beijing, China. pp.7, 2013
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 : mardi 11 septembre 2018 - 15:19:06
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'2013: 23rd International Joint Conference on Artificial Intelligence, 2013, Beijing, China. pp.7, 2013. 〈lirmm-00830330〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

394

Téléchargements de fichiers

375

Contact

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