Kernelization of Constraint Satisfaction Problems : A Study through Universal Algebra. / Lagerkvist, Victor; Wahlstrom, Magnus.

Principles and Practice of Constraint Programming: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Proceedings. Springer, 2017. p. 157-171 (Lecture Notes in Computer Science; Vol. 10416).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Documents

Abstract

A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given problem admits a kernel of a particular size. In this paper, we take an algebraic approach to the problem of characterizing the kernelization limits of NP-hard CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a finite-domain CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP which is preserved by a Maltsev operation. This result utilise a variant of the simple algorithm for Maltsev constraints. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization for Boolean CSPs with linear kernels, by showing that an algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP ⊆⊆ co-NP/poly.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Proceedings
PublisherSpringer
Pages157-171
Number of pages15
ISBN (Electronic)978-3-319-66158-2
ISBN (Print)978-3-319-66157-5
DOIs
StatePublished - 23 Aug 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume10416
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28357499