Networks

Bart Jansen and Astrid Pieterse win Excellent Student 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

This paper studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai’s study of the time complexity with respect to these parameters. Our results show that the existence of polynomial kernels for q-Coloring parameterized by the vertex-deletion distance to a graph class F is strongly related to the existence of a function f(q) which bounds the number of vertices which are needed to preserve the no-answer to an instance of q-List Coloring on F.

 

You can find the paper here.

Learn more about IPEC 2017 on their website.