Bessiere C.Hebrard E.Hnich B.Kiziltan Z.Quimper C.-G.Walsh T.2023-06-162023-06-1620089.78E+12https://hdl.handle.net/20.500.14365/3963Cornell Univ. Intelligent Information Systems Inst.;Toyota Motor Engineering and Manufacturing North America Inc.;ACM/SIGART;Boeing23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08 -- 13 July 2008 through 17 July 2008 -- Chicago, IL -- 74777We 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. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.eninfo:eu-repo/semantics/closedAccessArtificial intelligenceComputer programmingConstraint theoryPacket networksApproximabilityBounded sizesConstraint programmingsConstraint propagationsDynamic programsGlobal constraintsParameterized complexitiesBionicsConference Object2-s2.0-57749193700