The Parameterized Complexity of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2008

The Parameterized Complexity of Global Constraints


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
Origin : Publisher files allowed on an open archive

Dates and versions

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


  • HAL Id : lirmm-00272791 , version 1


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 View
9 Download


Gmail Facebook X LinkedIn More