On the Kernelization of Global Constraints

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 metadatas

Cited literature [11 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 10, 2020 - 9:10:16 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. ⟨hal-01670318⟩

Share

Metrics

Record views

173

Files downloads

113