  We present several sparsification lower and upper bounds for classic problems
in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian
Cycle, and (Connected) Dominating Set, we prove that there is no
polynomial-time algorithm that reduces any n-vertex input to an equivalent
instance, of an arbitrary problem, with bitsize O(n^{2-e}) for e > 0, unless NP
is in coNP/poly and the polynomial-time hierarchy collapses. These results
imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf
Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be
improved to have O(k^{2-e}) edges, unless NP is in coNP/poly. We also present a
positive result and exhibit a non-trivial sparsification algorithm for
d-Not-All-Equal SAT. We give an algorithm that reduces an n-variable input with
clauses of size at most d to an equivalent input with O(n^{d-1}) clauses, for
any fixed d. Our algorithm is based on a linear-algebraic proof of Lovasz that
bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex
hypergraphs by n choose d-1. We show that our kernel is tight under the
assumption that NP is not a subset of coNP/poly.

Computational Complexity;Data Structures and Algorithms