The Parameterized Complexity of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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⟩
182 Consultations
16 Téléchargements

Partager

More