Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs

Résumé : Les problèmes de satisfaction de contraintes (CSP) constituent une puissante manière de capturer de nombreux problèmes combinatoires. Le CSP général est connu pour être NP-complet, mais la complexité du problème paramétré CSP(S) dépend uniquement de son paramètre, habituellement un ensemble de relations sur lesquelles les contraintes sont construites. Suivant ce paramètre, il existe des instances de CSP “faciles” et “difficiles”. Dans cet article, nous montrons un théorème dichotomique pour tous domaines finis de CSP où la disjonction entre contraintes est autorisée. Cette dichotomie est basée sur un critère simple, nous permettant de classer les CSP disjonctifs comme étant dans P ou étant NP-complet. Nous prouvons également que le méta-problème, à savoir vérifier le critère de dichotomie pour les problèmes de satisfaction de contraintes disjonctifs, est fixed-parameter tractable. De plus, nous présentons un algorithme en temps polynomial répondant à cette question pour les CSP disjonctifs sur un domaine ternaire.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.209-218, 2008
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291615
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 15:58:23
Dernière modification le : jeudi 10 mai 2018 - 02:06:50
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:56:29

Fichier

pages-209-218-article6.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291615, version 1

Collections

Citation

Miki Hermann, Florian Richoux. Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.209-218, 2008. 〈inria-00291615〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

42