Kernels for Global Constraints

Details Kernels for Global Constraints Kernels for Global Constraints

2011-04-13

arxiv.org/abs/1104.2541v1

Computer Science

Artificial Intelligence

Scientific paper

Bessiere et al. (AAAI'08) showed that several intractable global constraints can be efficiently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is fixed-parameter tractable in k - the number of holes in domains - whenever bound consistency can be enforced in polynomial time; this applies to the global constraints AtMost-NValue and Extended Global Cardinality (EGC). In this paper we extend this line of research and introduce the concept of reduction to a problem kernel, a key concept of parameterized complexity, to the field of global constraints. In particular, we show that the consistency problem for AtMost-NValue constraints admits a linear time reduction to an equivalent instance on O(k^2) variables and domain values. This small kernel can be used to speed up the complete propagation of NValue constraints. We contrast this result by showing that the consistency problem for EGC constraints does not admit a reduction to a polynomial problem kernel unless the polynomial hierarchy collapses.

Affiliated with

Also associated with

No associations

Rating

Kernels for 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 Kernels for Global Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kernels for Global Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219243