Abstract
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
