Computer Science – Artificial Intelligence
Scientific paper
2009-03-03
AAAI-2008, 235-240, 2008
Computer Science
Artificial Intelligence
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence
Scientific paper
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 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.
Bessiere Christian
Hebrard Emmanuel
Hnich Brahim
Kiziltan Zeynep
Walsh Toby
No associations
LandOfFree
The Parameterized Complexity of Global Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Parameterized Complexity of Global Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Parameterized Complexity of Global Constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652781