ML Anthology

On the Kernelization of Global Constraints

Clément Carbonnel, Emmanuel Hebrard
IJCAI 2017 pp. 578-584
doi:10.24963/IJCAI.2017/81 /ijcai/2017/carbonnel2017ijcai-kernelization/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Carbonnel and Hebrard. "On the Kernelization of Global Constraints." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/81

Markdown

[Carbonnel and Hebrard. "On the Kernelization of Global Constraints." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/carbonnel2017ijcai-kernelization/) doi:10.24963/IJCAI.2017/81

BibTeX

@inproceedings{carbonnel2017ijcai-kernelization,
  title     = {{On the Kernelization of Global Constraints}},
  author    = {Carbonnel, Clément and Hebrard, Emmanuel},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {578-584},
  doi       = {10.24963/IJCAI.2017/81},
  url       = {https://mlanthology.org/ijcai/2017/carbonnel2017ijcai-kernelization/}
}