Skip to Main content Skip to Navigation
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

https://hal.laas.fr/hal-01670318
Contributor : Emmanuel Hebrard Connect in order to contact the contributor
Submitted on : Thursday, December 21, 2017 - 11:52:35 AM
Last modification on : Monday, July 4, 2022 - 8:51:14 AM

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. ⟨hal-01670318⟩

Share

Metrics

Record views

67

Files downloads

6