2025/06/20 by Retschmeier, Lukas
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.17485
For a given graph G = (V, E), a subset of the vertices D⊆ V is called a semitotal dominating set, if D is a dominating set and every vertex v ∈ D is within distance two to another witness v' ∈ D. We want to find a semitotal dominating set of minimum cardinality. We show that the problem is W[2]-hard on bipartite and split graphs when parameterized by the solution size k. On the positive side, we extend the kernelization technique of Alber, Fellows, and Niedermeier [JACM 2004] to obtain a linear kernel of size 358k on planar graphs. This result complements known linear kernels already known for several variants, including Total, Connected, Red-Blue, Efficient, Edge, and Independent Dominating Set.