On the Kernelization of Global Constraints

On the Kernelization of Global Constraints

Clément Carbonnel, Emmanuel Hebrard

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 578-584. https://doi.org/10.24963/ijcai.2017/81

Kernelization is a powerful concept from parameterized complexity theory that captures (a certain idea of) efficient polynomial-time preprocessing for hard decision problems. However, exploiting this technique in the context of constraint programming is challenging. Building on recent results for the VertexCover constraint, we introduce novel "loss-less" kernelization variants that are tailored for constraint propagation. We showcase the theoretical interest of our ideas on two constraints, VertexCover and EdgeDominatingSet.
Keywords:
Constraints and Satisfiability: Global Constraints
Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning
Constraints and Satisfiability: Constraints and Satisfiability