Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT

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‐\mathit{ϵ}})$ for $\mathit{ϵ}>0$ , unless $‐{NP}\subseteq ‐{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‐\mathit{ϵ}})$ edges, unless $‐{NP}\subseteq ‐{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 Lovász that bounds the number of hyperedges in critically 3‐chromatic d‐uniform n‐vertex hypergraphs by $\left(\begin{array}{c}n\\ d-1\end{array}\right)$ . We show that our kernel is tight under the assumption that $‐{NP}\subseteq ‐{coNP}/‐{poly}$ .