A Linear Kernel for Planar Semitotal Domination
cs.DS
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: A set of vertices S in a graph G is a semitotal dominating set if S is a dominating set and every vertex in S has a witness, that is, another vertex in S within distance at most two.
Abstract
A set of vertices S in a graph G is a semitotal dominating set if S is a dominating set and every vertex in S has a witness, that is, another vertex in S within distance at most two. The Semitotal Domination problem asks whether G admits such a set of size at most k. We study this problem parameterized by the solution size. We provide a linear kernel of size 358k on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is W[2] -hard on split graphs, on bipartite graphs and on t-claw-free graphs, it is W[1] -hard on circle graphs.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles