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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00272791
Contributor : Christian Bessiere <>
Submitted on : Friday, April 11, 2008 - 7:27:24 PM
Last modification on : Monday, June 15, 2020 - 1:38:03 PM

File

aaai08.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00272791, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

288

Files downloads

15