Skip to Main content Skip to Navigation
New interface
Conference papers

On the Kernelization of Global Constraints

Clément Carbonnel 1 Emmanuel Hébrard 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Emmanuel Hebrard Connect in order to contact the contributor
Submitted on : Thursday, December 21, 2017 - 11:52:35 AM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM


Files produced by the author(s)


  • HAL Id : hal-01670318, version 1


Clément Carbonnel, Emmanuel Hébrard. On the Kernelization of Global Constraints. International Joint Conference on Artificial Intelligence (IJCAI 2017), Aug 2017, Melbourne, Australia. 7p. ⟨hal-01670318⟩



Record views


Files downloads