Optimal data reduction for graph coloring using low-degree polynomials

Bart M.P. Jansen (Corresponding author), Astrid Pieterse

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
20 Downloads (Pure)

Abstract

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(kq−1logk) for q-Coloring parameterized by Vertex Cover for any q≥3 . This size bound is optimal up to ko(1) factors assuming NP⊈coNP/poly , and improves on the previous-best kernel of size O(kq) . 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)logk) . 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(n2−ε) for any ε>0 . Previously, such a lower bound was only known for coloring with q≥4 colors.
Original languageEnglish
Pages (from-to)3865-3889
Number of pages25
JournalAlgorithmica
Volume81
Issue number10
DOIs
Publication statusPublished - 1 Oct 2019

Keywords

  • Graph coloring
  • Graph homomorphism
  • Kernelization

Fingerprint Dive into the research topics of 'Optimal data reduction for graph coloring using low-degree polynomials'. Together they form a unique fingerprint.

Cite this