Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291615
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 3:58:23 PM
Last modification on : Thursday, March 5, 2020 - 6:24:56 PM
Long-term archiving on: : Friday, May 28, 2010 - 10:56:29 PM

File

pages-209-218-article6.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291615, version 1

Collections

Citation

Miki Hermann, Florian Richoux. Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.209-218. ⟨inria-00291615⟩

Share

Metrics

Record views

174

Files downloads

66