The Parameterized Complexity of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

The Parameterized Complexity of Global Constraints

Résumé

We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have natural parameters which make them fixed- parameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symme- try breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symme- tries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation.
Fichier principal
Vignette du fichier
aaai08.pdf (198.92 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00272791 , version 1 (11-04-2008)

Identifiants

  • HAL Id : lirmm-00272791 , version 1

Citer

Christian Bessiere, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Claude-Guy Quimper, et al.. The Parameterized Complexity of Global Constraints. AAAI Conference on Artificial Intelligence, Jul 2008, Chicago, IL, United States. pp.235-240. ⟨lirmm-00272791⟩
164 Consultations
9 Téléchargements

Partager

Gmail Facebook X LinkedIn More