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 [Toulouse]
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
International Joint Conference on Artificial Intelligence (IJCAI 2017), Aug 2017, Melbourne, Australia. 7p., 2017
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal.laas.fr/hal-01670318
Contributor : Emmanuel Hebrard <>
Submitted on : Thursday, December 21, 2017 - 11:52:35 AM
Last modification on : Friday, January 19, 2018 - 4:00:17 PM

File

ijcai2017.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01670318, version 1

Citation

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., 2017. 〈hal-01670318〉

Share

Metrics

Record views

20

Files downloads

4