Improved linear problem kernel for planar connected dominating set

In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph  G=(V,E) and a non-negative integer  k, asks for a subset  D⊆V with  ∣D∣≤k such that  D forms a dominating set of  G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most  130k vertices, improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size.