 |
HAL-LIRMM - Open Archive |  |
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.
Cited literature [29 references]
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
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