Research On The Kernelization Of Several Domination Problems On Planar Graph

Dominating Set problem is a very important problem for its wide applications such as wireless sensor networks routing, computational biology, election, guard patrol, facilities location and so on.Former research proves that this problem is not only an NP-hard problem but also a W[2]-complete problem under the parameterized complexity theory, which suggests that it is not likely to design an efficient algorithm to solve this problem. Recently, people approached dominating set problem from special graphs which turns out to be very fruitful. It has been proved that this problem is Fixed-parameterized tractable (FPT) and has a polynomial kernel on Kij-free graph at the moment.We continue this line of research, and in this paper we focuse on the kernelization of three variations of dominating set problem, namely, Planar c-Connected m-Dominating Set problem, Planar m-tuple Dominating Set problem and Planar Total m-Domianting Set problem. Using region decomposition technology, we give linear kernels for all of them which suggest that these three problems are FPT and show that the results are tight.Based on the problems metioned above, we define a more general version, namely, c-Connected (mα,mβ)-Dominating Set problem. Firstly, we prove that the problem is still NP-Complete on planar graph when mβ≥mα≥0. Secondly, we show that a c-Connected (mα,mβ)-Dominating Set is also an (max(c,mα),mβ)-Dominating Set which decreases the parameters to two. Finally, we propose a general reduction rule to achieve the results that the problem has a linear size kernel as (max(c,mα)+6)x(3|S|-6) when mβ≤2 and mα×mβ×max(c,1)≠1, and an(mβ|S|-4)/(mβ-2) kernel when mβ≥3.