  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 Boolean satisfiability problem
(SAT), and 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 SAT
problem admits a kernel of a particular size. This could be contrasted to the
currently flourishing research program of determining the classical complexity
of finite-domain CSP problems, where almost all non-trivial tractable classes
have been identified with the help of algebraic properties. In this paper, we
take an algebraic approach to the problem of characterizing the kernelization
limits of NP-hard SAT and 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 CSP
problem has a kernel with O(n) constraints if it can be embedded (via a domain
extension) into a CSP problem which is preserved by a Maltsev operation. We
also study extensions of this towards SAT and CSP problems with kernels with
O(n^c) constraints, c>1, based on embeddings into CSP problems preserved by a
k-edge operation, k > c. These results follow via a variant of the celebrated
few subpowers algorithm. In the complementary direction, we give indication
that the Maltsev condition might be a complete characterization of SAT problems
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 is included in co-NP/poly.
