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 130 k 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.

Authors

• Weizhong Luo
• Jianxin Wang
• Qilong Feng
• Jiong Guo
• Jianer Chen

Keywords

• Data reduction
• Region decomposition
• Kernelization
• Connected dominating set