Networks

Bart Jansen and Astrid Pieterse win Best Paper award at IPEC 2017

Bart Jansen (Assistant Professor) and Astrid Pieterse (PhD student) won the "Excellent Student Paper Award" at the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) in Vienna, Austria, with their paper "Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials".

 

Bart and Astrid

Abstract of the paper

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 use a recent technique of finding redundant constraints by representing them as low-degree polynomials, to 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 is not in coNP/poly, and improves on the previous-best kernel of size O(k^q). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP is not in coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^(2−e)) for any e > 0. Until now, such a lower bound was only known for coloring with q >= 4 colors.

 

You can find the paper here.

Learn more about IPEC 2017 on their website.