Hans Bodlaender (Utrecht University)
Kernelization for Pathwidth
Abstract: In this talk, we look at kernelization algorithms for pathwidth. A number of safe reduction rules for pathwidth are given. It is shown that these rules give a kernel with a number of vertices that is cubic in the size of a vertex cover of the graph. We also discuss for other graph parameters whether there exist a kernel of size polynomial in these parameters for the pathwidth problem.