Skip to Main content Skip to Navigation
Conference papers

The Parameterized Complexity of Global Constraints

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

Cited literature [29 references]  Display  Hide  Download
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Friday, April 11, 2008 - 7:27:24 PM
Last modification on : Friday, August 5, 2022 - 3:02:57 PM


Publisher files allowed on an open archive


  • HAL Id : lirmm-00272791, version 1



Christian Bessière, 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⟩



Record views


Files downloads