Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

• Published in: Algorithmica 2019-10, Vol.81 (10), p.3865-3889
• Main Authors: Jansen, Bart M. P., Pieterse, Astrid
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Computer Science; Computer Systems Organization and Communication Networks; Data reduction; Data Structures and Information Theory; Graph coloring; Homomorphisms; Kernels; Lower bounds; Mathematics of Computing; Parameterization; Parameters; Polynomials; Special Issue: Parameterized and Exact Computation; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-019-00578-5

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 O ( k q - 1 log k ) for q - Coloring parameterized by Vertex Cover for any q ≥ 3 . This size bound is optimal up to  k o ( 1 ) factors assuming  NP ⊈ coNP / poly , and improves on the previous-best kernel of size  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 O ( k Δ ( H ) log k ) . Our second result shows that 3- Coloring does not admit non-trivial sparsification: assuming NP ⊈ coNP / poly , the parameterization by the number of vertices  n admits no (generalized) kernel of size  O ( n 2 - ε ) for any ε > 0 . Previously, such a lower bound was only known for coloring with q ≥ 4 colors.