Detecting and Exploiting Subproblem Tractability - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Detecting and Exploiting Subproblem Tractability

Résumé

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.
Fichier principal
Vignette du fichier
ijcai13-tractability.pdf (242.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00830330 , version 1 (04-06-2013)

Identifiants

  • HAL Id : lirmm-00830330 , version 1
  • PRODINRA : 263216

Citer

Christian Bessiere, 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. pp.468-474. ⟨lirmm-00830330⟩
316 Consultations
277 Téléchargements

Partager

Gmail Facebook X LinkedIn More