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

National audienceLes 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