Jansen, Bart M. P. ;
Pieterse, Astrid
Optimal Data Reduction for Graph Coloring Using LowDegree Polynomials
Abstract
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a qColoring 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 qColoring.
First, we use a recent technique of finding redundant constraints by representing them as lowdegree polynomials, to obtain a kernel of bitsize O(k^(q1) log k) for qColoring parameterized by Vertex Cover for any q >= 3. This size bound is optimal up to k^o(1) factors assuming NP is not a subset of coNP/poly, and improves on the previousbest kernel of size O(k^q). Our second result shows that 3Coloring does not admit nontrivial sparsification: assuming NP is not a subset of coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^(2e)) for any e > 0. Previously, such a lower bound was only known for coloring with q >= 4 colors.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2018:8550,
author = {Bart M. P. Jansen and Astrid Pieterse},
title = {{Optimal Data Reduction for Graph Coloring Using LowDegree Polynomials}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {22:122:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8550},
URN = {urn:nbn:de:0030drops85500},
doi = {10.4230/LIPIcs.IPEC.2017.22},
annote = {Keywords: graph coloring, kernelization, sparsification}
}
2018
Keywords: 

graph coloring, kernelization, sparsification 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

2018 