Kernelizability of Min Ones CSPs

kernelizations for Min Ones CSP problems; joint work with Stefan
Kratsch.

A kernelization is a type of polynomial time pre-processing with a
size guarantee for the result. The canonical example is Vertex Cover:
Given a graph G and an upper bound k on the size of the vertex cover,
we can in polynomial time reduce G to have only 2k vertices (and a
total size of O(k^2)). Over the last year or so, establishing upper
and lower bounds on the possible kernelization guarantees for various
problems has seen a lot of attention (in particular, the existence
of polynomial-sized kernels).

We consider here Min Ones CSPs, where the input is a conjunctive
formula F over some type of constraints, and a number k, and a solution to F with at most k true variables is sought.
Depending on the types of constraints allowed, this captures different
problems, such as Vertex Cover, Min Ones 3SAT, or Nearest Codeword.
It turns out that some such problem variants admit polynomial-sized kernels, while others do not (unless the polynomial hierarchy collapses).

We present here a condition on the constraints, dubbed mergeability,
that determines whether a certain problem variant allows a
kernelization to a polynomial-sized kernel or not. Specifically, if
all allowed constraints are mergeable, then there is a kernelization
to a polynomial-sized kernel, but if any non-mergeable constraint
type is allowed, then either the problem is polynomial-time solvable, or there is no kernelization to polynomial size unless the polynomial hierarchy collapses.