A Linear Kernel for Planar Semitotal Domination

arXiv:2610.37295 · cs.DS · Submitted 2026-10-27 · Read on arXiv

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