A linear kernel for planar total dominating set

摘要: A total dominating set of a graph $G=(V,E)$ is subset $D \subseteq V$ such that every vertex in $V$ adjacent to some $D$. Finding minimum size NP-hard on planar graphs and W[2]-complete general when parameterized by the solution size. By meta-theorem Bodlaender et al. [J. ACM, 2016], there exists linear kernel for Total Dominating Set bounded genus. Nevertheless, it not clear how can be effectively constructed, obtain explicit reduction rules with reasonably small constants. Following approach Alber 2004], we provide an at most $410k$ vertices, where $k$ solution. This result complements several known constructive kernels other domination problems as Set, Edge Efficient Connected or Red-Blue Set.