Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
Bart M. P. Jansen, Astrid Pieterse · Algorithmica · 2019
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we obtain a kernel of bitsize $${\mathcal {O}}(k^{q-1}\log {k})$$ for q-Coloring parameterized by Vertex Cover for any $$q\ge 3$$ . This size bound is optimal up to $$k^{o(1)}$$ factors assuming $$\mathsf {NP} ot \subseteq \mathsf {coNP/poly}$$ , and improves on the previous-best kernel of size $${\mathcal {O}}(k^q)$$ . We generalize this result for deciding q-colorability of a graph G, to deciding the existence of a homomorphism from G to an arbitrary fixed graph H. Furthermore, we can replace the parameter vertex cover by the less restrictive parameter twin-cover. We prove that H-Coloring parameterized by Twin-Cover has a kernel of size $${\mathcal {O}}(k^{\varDelta (H)}\log k)$$ . Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming $$\mathsf {NP} ot \subseteq \mathsf {coNP/poly}$$ , the parameterization by the number of vertices n admits no (generalized) kernel of size $${\mathcal {O}}(n^{2-\varepsilon })$$ for any $$\varepsilon > 0$$ . Previously, such a lower bound was only known for coloring with $$q \ge 4$$ colors.