The Parameterized Complexity of Global Constraints

Simple item page
dc.creatorBessiere, Christian
dc.creatorHebrard, Emmanuel
dc.creatorHnich, Brahim
dc.creatorKiziltan, Zeynep
dc.creatorWalsh, Toby
dc.date2009-03-03
dc.date.accessioned2026-07-07T12:48:36Z
dc.date.available2026-07-07T12:48:36Z
dc.descriptionWe 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 symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation.
dc.descriptionProceedings of the Twenty-Third AAAI Conference on Artificial Intelligence
dc.identifierhttps://arxiv.org/abs/0903.0467
dc.identifierhttp://arxiv.org/abs/0903.0467
dc.identifierAAAI-2008, 235-240, 2008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222114
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectI.2.4
dc.titleThe Parameterized Complexity of Global Constraints
dc.typetext

Files

Collections

arXiv